QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877935 | #8302. Incoming Asteroids | December456 | WA | 117ms | 118632kb | C++14 | 2.3kb | 2025-02-01 12:28:30 | 2025-02-01 12:28:33 |
Judging History
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'