QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#877935#8302. Incoming AsteroidsDecember456WA 117ms118632kbC++142.3kb2025-02-01 12:28:302025-02-01 12:28:33

Judging History

你现在查看的是最新测评结果

  • [2025-02-01 12:28:33]
  • 评测
  • 测评结果:WA
  • 用时:117ms
  • 内存:118632kb
  • [2025-02-01 12:28:30]
  • 提交

answer

#include <algorithm>
#include <cstdio>
#include <vector>

constexpr int MAXN = 200000 + 2;
constexpr int MAXK = 3;
constexpr int MAXLOGN = 20 + 2;

class Observatory {
  public:
    int b, cnt, warnId[MAXK];
    long long lim;
} ob[MAXN];

long long a[MAXN];

std::vector<int> ans, vec[MAXN][MAXLOGN];

int f(int x, int b) {
    return ((x >> b) + 1) << b;
}

bool valid(int x) {
    long long sum = 0;

    for (int i = 0; i < ob[x].cnt; i ++) {
        sum += f(a[ob[x].warnId[i]], ob[x].b) - 1;
    }

    return sum < ob[x].lim;
}

bool update(int x) {
    while (ob[x].b >= 0 && !valid(x)) {
        ob[x].b --;
    }
    return ob[x].b >= 0;
}

void insert(int x) {
    for (int i = 0; i < ob[x].cnt; i ++) {
        vec[ob[x].warnId[i]][ob[x].b].push_back(x);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    while (m --) {
        static int last = 0, id = 0;

        int op;
        scanf("%d", &op);

        if (op == 1) {
            id ++;

            scanf("%lld%d", &ob[id].lim, &ob[id].cnt);

            int *seq = ob[id].warnId;

            ob[id].lim ^= last;
            ob[id].b = MAXLOGN;

            for (int i = 0; i < ob[id].cnt; i ++) {
                scanf("%d", &seq[i]);

                ob[id].lim += a[seq[i] ^= last];
            }

            while (!valid(id)) {
                ob[id].b --;
            }

            insert(id);
        } else {
            int x, y;
            scanf("%d%d", &x, &y);

            a[x ^= last] += y ^= last;

            ans.clear();

            for (int b = 0; b < MAXLOGN; b ++) {
                if (!vec[x][b].size() ||
                  a[x] < f(a[x] - y, b)) {
                    continue;
                }

                std::vector<int> tmp;

                for (int id : vec[x][b]) {
                    if (update(id)) {
                        tmp.push_back(id);
                    } else {
                        ans.push_back(id);
                    }
                }

                vec[x][b] = tmp;
            }

            std::sort(ans.begin(), ans.end());

            printf("%d", last = ans.size());

            for (int x : ans) {
                printf(" %d", x);
            }

            putchar('\n');
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 109460kb

input:

3 5
1 5 3 1 2 3
2 2 1
1 2 2 1 2
2 3 1
2 1 3

output:

0
0
2 1 2

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 117ms
memory: 118632kb

input:

200000 200000
1 421386 1 122023
2 127573 97972
1 489180 1 197930
2 82505 59100
1 502097 3 91617 14193 139642
2 132931 74031
1 404862 1 36227
2 152826 8462
1 750072 2 51616 75416
2 1547 11479
1 255849 2 70036 41620
2 126414 17120
1 626334 3 97273 190595 174083
2 148803 132
1 407236 2 83898 5103
2 169...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 8615th lines differ - expected: '0', found: '1 2570'