QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #861607 | #9727. Barkley III | Andyqian7 | TL | 465ms | 78448kb | C++20 | 4.4kb | 2025-01-18 18:33:09 | 2025-01-18 18:33:21 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, s, e) for (int i = s; i <= e; i++)
#define int long long
using namespace std;
const int N = 1e6 + 10;
struct info
{
signed ind[64];
} tr[N << 2];
int n, q, a[N], lz[N << 2];
info operator+(const info &a, const info &b)
{
info ret;
rep(i, 0, 62)
{
if (a.ind[i] == -1 && b.ind[i] == -1)
ret.ind[i] = -1;
else if (a.ind[i] == 0 || b.ind[i] == 0)
ret.ind[i] = 0;
else if (a.ind[i] > 0 && b.ind[i] > 0)
ret.ind[i] = 0;
else if (a.ind[i] > 0)
ret.ind[i] = a.ind[i];
else
ret.ind[i] = b.ind[i];
}
return ret;
}
void pushup(int m)
{
tr[m] = tr[m << 1] + tr[m << 1 | 1];
}
void pushdown(int m, int l, int r)
{
int mid = l + r >> 1;
lz[m << 1] &= lz[m], lz[m << 1 | 1] &= lz[m];
rep(i, 0, 62)
{
if (~lz[m] >> i & 1)
{
if (mid > l)
tr[m << 1].ind[i] = 0;
else
tr[m << 1].ind[i] = l;
if (r > mid + 1)
tr[m << 1 | 1].ind[i] = 0;
else
tr[m << 1 | 1].ind[i] = r;
}
}
rep(i, 0, 62)
lz[m] |= 1ll << i;
}
void build(int l, int r, int m)
{
rep(i, 0, 62)
lz[m] |= 1ll << i;
if (l == r)
{
rep(i, 0, 62)
{
if (a[l] >> i & 1)
{
tr[m].ind[i] = -1;
}
else
{
tr[m].ind[i] = l;
}
}
return;
}
int mid = l + r >> 1;
build(l, mid, m << 1), build(mid + 1, r, m << 1 | 1);
pushup(m);
}
info query(int L, int R, int l, int r, int m)
{
if (L <= l && r <= R)
{
return tr[m];
}
pushdown(m, l, r);
int mid = l + r >> 1;
info ret;
memset(ret.ind, 255, sizeof ret.ind);
if (L <= mid)
ret = ret + query(L, R, l, mid, m << 1);
if (R > mid)
ret = ret + query(L, R, mid + 1, r, m << 1 | 1);
return ret;
}
void update(int x, int s, int l, int r, int m)
{
if (l == r)
{
rep(i, 0, 62)
{
if (x >> i & 1)
{
tr[m].ind[i] = -1;
}
else
{
tr[m].ind[i] = l;
}
}
return;
}
pushdown(m, l, r);
int mid = l + r >> 1;
if (s <= mid)
update(x, s, l, mid, m << 1);
if (s > mid)
update(x, s, mid + 1, r, m << 1 | 1);
pushup(m);
}
void update(int L, int R, int x, int l, int r, int m)
{
if (L <= l && r <= R)
{
lz[m] &= x;
rep(i, 0, 62)
{
if (~lz[m] >> i & 1)
{
if (r > l)
tr[m].ind[i] = 0;
else
tr[m].ind[i] = l;
}
}
return;
}
pushdown(m, l, r);
int mid = l + r >> 1;
if (L <= mid)
update(L, R, x, l, mid, m << 1);
if (R > mid)
update(L, R, x, mid + 1, r, m << 1 | 1);
pushup(m);
}
template <typename T>
inline void qr(T &x)
{
x = 0;
int f = 0;
char s = getchar();
while (s < '0' || '9' < s)
f |= s == '-', s = getchar();
while ('0' <= s && s <= '9')
x = x * 10 + s - 48, s = getchar();
x = f ? -x : x;
}
signed main()
{
qr(n), qr(q);
rep(i, 1, n) qr(a[i]);
build(1, n, 1);
while (q--)
{
int tp;
qr(tp);
if (tp == 1)
{
int l, r, x;
qr(l), qr(r), qr(x);
update(l, r, x, 1, n, 1);
}
else if (tp == 2)
{
int s, x;
qr(s), qr(x);
update(x, s, 1, n, 1);
}
else
{
int l, r;
qr(l), qr(r);
info ret = query(l, r, 1, n, 1);
int ans = 0, del = 0;
for (int i = 62; ~i; i--)
{
if (!del && ret.ind[i] > 0)
{
del = ret.ind[i];
}
if (ret.ind[i] == -1)
{
ans |= 1ll << i;
}
if (del && ret.ind[i] == del)
{
ans |= 1ll << i;
}
}
printf("%lld\n", ans);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8008kb
input:
5 9 7 7 7 6 7 3 1 5 2 1 3 3 1 5 3 1 3 1 1 2 3 3 1 3 2 2 8 3 1 3 3 1 2
output:
7 6 7 3 3 8
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7872kb
input:
10 10 6760061359215711796 1568091718842717482 1568091718842717482 1568091718842717482 5232472783634052627 8795942500783873690 1568091718842717482 1568091718842717482 1568091718842717482 1568091718842717482 1 3 5 7587422031989082829 3 6 10 1 7 8 5197616143400216932 2 4 2518604563805514908 2 2 4533959...
output:
1568091718842717482 35184908959744 176025477579040 8795942500783873690
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 8004kb
input:
100 100 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 625967318191814868 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072...
output:
576531121047601152 1 576460752303423488 4263579105072360993 1306043896232411137 4263579105072360993 576531121047601152 633397148123136 0 1153488865559840256 1152922054496880128 1730020640668059136 3533641810948498945 67108864 1730020640668059136 0 633397148123136 1729382296723653632 0 17300206406680...
result:
ok 78 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 7812kb
input:
1000 1000 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3639580211161047627 3368486440884437410 3368486440884437410 3368486440...
output:
3368486440884437410 3368486440884437410 3368486440884437410 2251799981457408 0 0 3368486440884437410 0 3326828075601101216 592509842556584322 0 0 0 0 0 0 37154696925806592 0 0 0 3368486440884437410 0 0 3368486440884437410 0 578998425140330496 0 0 134217728 0 3368486440884437410 2306405959167115264 0...
result:
ok 732 lines
Test #5:
score: 0
Accepted
time: 465ms
memory: 78448kb
input:
100000 100000 4364025563773184234 7745126251050571359 5111681002836044963 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7222555899134537718 7745126251050571359 686495...
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 4613942216556019776 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
ok 75105 lines
Test #6:
score: -100
Time Limit Exceeded
input:
1000000 1000000 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485...
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 8796093022208 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 576460754450907136 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...