QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352430 | #6427. Just Another Game of Stones | PorNPtree | WA | 866ms | 76376kb | C++14 | 3.6kb | 2024-03-13 11:05:42 | 2024-03-13 11:05:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], mn[1 << 19], mn2[1 << 19], cnt[1 << 19], lazy[1 << 19], fxor[1 << 19], z[30][1 << 19];
void addTag(int k, int x)
{
// assert(mn2[k] >= x);
if (cnt[k] & 1) {
fxor[k] ^= mn[k] ^ x;
}
for (int i = 0; i < 30; ++i) {
if ((mn[k] >> i) & 1) {
z[i][k] -= cnt[k];
}
if ((x >> i) & 1) {
z[i][k] += cnt[k];
}
}
mn[k] = x;
lazy[k] = x;
return;
}
void pushdown(int k)
{
if (lazy[k]) {
if (mn[k << 1] < lazy[k]) {
addTag(k << 1, lazy[k]);
}
if (mn[k << 1 | 1] < lazy[k]) {
addTag(k << 1 | 1, lazy[k]);
}
lazy[k] = 0;
}
return;
}
void pushup(int k)
{
fxor[k] = fxor[k << 1] ^ fxor[k << 1 | 1];
for (int i = 0; i < 30; ++i) {
z[i][k] = z[i][k << 1] + z[i][k << 1 | 1];
}
if (mn[k << 1] < mn[k << 1 | 1]) {
mn[k] = mn[k << 1];
cnt[k] = cnt[k << 1];
mn2[k] = min(mn2[k << 1], mn[k << 1 | 1]);
} else if (mn[k << 1] > mn[k << 1 | 1]) {
mn[k] = mn[k << 1 | 1];
cnt[k] = cnt[k << 1 | 1];
mn2[k] = min(mn2[k << 1 | 1], mn[k << 1]);
} else {
mn[k] = mn[k << 1];
cnt[k] = cnt[k << 1] + cnt[k << 1 | 1];
mn2[k] = min(mn2[k << 1], mn2[k << 1 | 1]);
}
return;
}
void build(int k, int l, int r)
{
lazy[k] = 0;
if (l == r) {
mn[k] = a[l];
mn2[k] = 1 << 30;
cnt[k] = 1;
fxor[k] = a[l];
for (int i = 0; i < 30; ++i) {
z[i][k] = (a[l] >> i) & 1;
}
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
pushup(k);
return;
}
void modify(int k, int l, int r, int x, int y, int v)
{
if (l > y || r < x || mn[k] >= v) {
return;
}
int mid = (l + r) >> 1;
if (l >= x && r <= y) {
if (mn2[k] >= x) {
addTag(k, v);
} else {
// assert(l != r);
pushdown(k);
modify(k << 1, l, mid, x, y, v);
modify(k << 1 | 1, mid + 1, r, x, y, v);
pushup(k);
}
return;
}
pushdown(k);
modify(k << 1, l, mid, x, y, v);
modify(k << 1 | 1, mid + 1, r, x, y, v);
pushup(k);
return;
}
int f[30];
int query(int k, int l, int r, int x, int y)
{
if (l > y || r < x) {
return 0;
}
if (l >= x && r <= y) {
for (int i = 0; i < 30; ++i) {
f[i] += z[i][k];
}
return fxor[k];
}
pushdown(k);
int mid = (l + r) >> 1;
return query(k << 1, l, mid, x, y) ^
query(k << 1 | 1, mid + 1, r, x, y);
}
signed main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (q--) {
int opt, l, r, x;
scanf("%d%d%d%d", &opt, &l, &r, &x);
if (opt == 1) {
if (x) {
modify(1, 1, n, l, r, x);
}
} else {
for (int i = 0; i < 30; ++i) {
f[i] = 0;
}
int fx = query(1, 1, n, l, r) ^ x;
if (!fx) {
puts("0");
} else {
int k = 31 - __builtin_clz(fx);
// assert(k < 30);
printf("%d\n", f[k] + ((x >> k) & 1));
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 75572kb
input:
5 4 1 2 1 4 1 2 1 3 1 1 2 4 3 2 2 4 4 2 1 4 4
output:
1 0 3
result:
ok 3 number(s): "1 0 3"
Test #2:
score: -100
Wrong Answer
time: 866ms
memory: 76376kb
input:
200000 200000 962352030 173642520 1008864183 74920228 684681800 500911321 1001441054 257633652 185843534 59168654 317689197 731348417 123888883 708119712 340055368 876566011 980078202 969174443 814012870 715639041 596932238 173757742 314504576 1045746913 740811577 570187156 999816627 12441059 122507...
output:
38889 57353 46659 19709 28979 92881 2495 627 9899 29441 6995 6189 16887 8329 21013 10547 48695 8431 32233 361 16523 12411 75407 8773 38387 28179 9837 46941 24643 11285 15993 5011 18423 47919 93471 19785 1357 3113 6937 12699 4623 17895 19869 55667 76027 27369 60745 83197 50853 86885 7639 50175 37955 ...
result:
wrong answer 5th numbers differ - expected: '34617', found: '28979'