QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425114 | #5022. 【模板】线段树 | APJifengc | 0 | 601ms | 15308kb | C++14 | 2.3kb | 2024-05-29 22:19:44 | 2024-05-29 22:19:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
const int B = 500;
int id;
int n, q, a[MAXN], b[MAXN], c[MAXN];
int qc, qt[MAXN], ql[MAXN], qr[MAXN], qx[MAXN], qid[MAXN];
int qq;
int bl[MAXN], L[MAXN], R[MAXN];
inline void update(int i, int cc) {
for (int j = 1; j <= cc; j <<= 1) if (cc & j) {
for (int k = R[i]; k - j >= max(1, L[i - 1]); k--) b[k] ^= b[k - j];
}
}
int ans[MAXN];
inline void rebuild() {
for (int i = (bl[n] == 1 ? 1 : 2); i <= bl[n]; i++) {
int ll = (i == 2 ? 1 : L[i]), rr = R[i];
for (int j = L[i - 1]; j <= R[i]; j++) b[j] = a[j];
int cc = 0;
for (int j = 1; j <= qc; j++) {
if (qt[j] == 1) {
if (qr[j] < L[i - 1] || ql[j] > R[i]) continue;
if (ql[j] <= L[i - 1] && R[i] <= qr[j]) {
cc++;
continue;
}
update(i, cc), cc = 0;
for (int k = min(R[i], qr[j]); k > max(L[i - 1], ql[j]); k--) b[k] ^= b[k - 1];
} else {
if (qx[j] < ll || qx[j] > rr) continue;
update(i, cc), cc = 0;
ans[qid[j]] = b[qx[j]];
}
}
update(i, cc);
for (int j = ll; j <= rr; j++) c[j] = b[j];
}
for (int i = 1; i <= n; i++) a[i] = c[i];
qc = 0;
}
int main() {
// freopen("xor.in", "r", stdin);
// freopen("xor.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> id >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int l = 1, r, i = 1; l <= n; l = r + 1, i++) {
r = min(n, l + B - 1);
L[i] = l, R[i] = r;
for (int j = l; j <= r; j++) bl[j] = i;
}
int tt = 0;
for (int i = 1; i <= q; i++) {
int op; cin >> op;
++qc;
if (op == 1) {
int l, r; cin >> l >> r;
qt[qc] = 1, ql[qc] = l, qr[qc] = r;
tt++;
} else {
int x; cin >> x;
qt[qc] = 2, qx[qc] = x, qid[qc] = ++qq;
}
if (tt == B) rebuild(), tt = 0;
}
rebuild();
for (int i = 1; i <= qq; i++) cout << ans[i] << '\n';
for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13952kb
input:
1 6 6 1 1 5 1 9 4 2 5 1 2 5 2 4 1 3 6 2 6 1 1 6
output:
9 4 12 9 4 12 0 0 0
result:
wrong answer 4th numbers differ - expected: '1', found: '9'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 577ms
memory: 14808kb
input:
2 249998 99999 1048488450 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 ...
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 50083rd numbers differ - expected: '1048488450', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 601ms
memory: 15092kb
input:
3 250000 99999 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...
output:
0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 ...
result:
wrong answer 50216th numbers differ - expected: '1', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 311ms
memory: 15308kb
input:
4 249996 99997 309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...
output:
611117059 866091251 300188933 0 478915924 1053588351 453142424 897441996 60971719 748656483 600408393 0 303761852 983037069 883016404 332332552 1069626159 860304528 851235295 561276840 389049294 681320982 484263000 351914192 620106464 667080579 733146026 375466744 0 347632358 737240082 321494160 0 3...
result:
wrong answer 49985th numbers differ - expected: '309331355', found: '611117059'
Subtask #5:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 368ms
memory: 13756kb
input:
5 249997 99997 860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...
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 1st numbers differ - expected: '860563869', found: '0'
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%