QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692496 | #8338. Quad Kingdoms Chess | snow_mikumiku | TL | 34ms | 10040kb | C++14 | 3.9kb | 2024-10-31 14:37:23 | 2024-10-31 14:37:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UL = unsigned long long;
const UL mi = 995329;
const int N = 1e5 + 10;
UL m995[N], a[N], b[N];
struct tree {
int l, r;
UL cnt;
UL max, hs, minstk;
friend tree operator + (tree &a, tree &b) {
tree ans;
ans.cnt = a.cnt + b.cnt;
ans.minstk = a.minstk;
ans.max = b.max;
ans.hs = a.hs * m995[b.cnt] + b.hs;
return ans;
}
}A[N << 3], B[N << 3], nul;
tree ask(int p, UL mx, int ty)
{
if(!ty) {
if(!A[p].l || A[p].max < mx) return nul;
if(A[p].minstk >= mx) return A[p];
tree tmp = ask(p * 2, mx, ty);
tree tmp2 = ask(p * 2 + 1, max(tmp.max, mx), ty);
return tmp + tmp2;
}
else {
if(!B[p].l) return nul;
if(B[p].minstk >= mx) return B[p];
tree tmp = ask(p * 2, mx, ty);
tree tmp2 = ask(p * 2 + 1, max(tmp.max, mx), ty);
return tmp + tmp2;
}
}
void update(int p, int ty)
{
int ls = p * 2, rs = p * 2 + 1;
if(!ty) {
if(A[ls].max > A[rs].max) {
A[p].cnt = A[ls].cnt;
A[p].hs = A[ls].hs;
A[p].max = A[ls].max;
A[p].minstk = A[ls].minstk;
}
else {
tree tmp;
if(A[ls].max <= A[rs].minstk) tmp = A[rs];
else tmp = ask(rs, A[ls].max, ty);
tmp = A[ls] + tmp;
A[p].cnt = tmp.cnt;
A[p].hs = tmp.hs;
A[p].max = tmp.max;
A[p].minstk = tmp.minstk;
}
}
else {
if(B[ls].max > B[rs].max) {
B[p].cnt = B[ls].cnt;
B[p].hs = B[ls].hs;
B[p].max = B[ls].max;
B[p].minstk = B[ls].minstk;
}
else {
tree tmp;
if(B[ls].max <= B[rs].minstk) tmp = B[rs];
else tmp = ask(rs, B[ls].max, ty);
tmp = B[ls] + tmp;
B[p].cnt = tmp.cnt;
B[p].hs = tmp.hs;
B[p].max = tmp.max;
B[p].minstk = tmp.minstk;
}
}
}
void build(int l, int r, int p, int ty)
{
if(!ty) {
A[p].l = l, A[p].r = r;
if(l == r) {
A[p].cnt = 1;
A[p].max = A[p].hs = A[p].minstk = a[l];
return;
}
}
else {
B[p].l = l, B[p].r = r;
if(l == r) {
B[p].cnt = 1;
B[p].max = B[p].hs = B[p].minstk = b[l];
return;
}
}
int mid = l + r >> 1;
build(l, mid, p * 2, ty);
build(mid + 1, r, p * 2 + 1, ty);
update(p, ty);
}
void change(int x, int p, UL To, int ty)
{
if(!ty) {
if(A[p].l == A[p].r && A[p].l == x) {
A[p].hs = A[p].max = A[p].minstk = To;
return;
}
int mid = A[p].l + A[p].r >> 1;
if(x <= mid) change(x, p * 2, To, ty);
else change(x, p * 2 + 1, To, ty);
update(p, ty);
}
else {
if(B[p].l == B[p].r && B[p].l == x) {
B[p].hs = B[p].max = B[p].minstk = To;
return;
}
int mid = B[p].l + B[p].r >> 1;
if(x <= mid) change(x, p * 2, To, ty);
else change(x, p * 2 + 1, To, ty);
update(p, ty);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
m995[0] = 1;
for(int i = 1; i < N; i++) m995[i] = m995[i - 1] * mi;
int n, m, q;
cin >> n;
for(int i = n; i >= 1; i--) cin >> a[i];
cin >> m;
for(int i = m; i >= 1; i--) cin >> b[i];
build(1, n, 1, 0);
build(1, m, 1, 1);
int op, x, y;
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> op >> x >> y;
if(op == 1) x = n - x + 1, change(x, 1, y, 0);
if(op == 2) x = m - x + 1, change(x, 1, y, 1);
if(B[1].hs == A[1].hs) cout << "YES\n";
else cout << "NO\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10040kb
input:
5 1 2 3 4 5 5 5 4 3 2 1 8 1 1 5 1 4 2 1 2 4 1 5 1 1 5 5 2 1 4 2 3 5 2 5 5
output:
NO NO NO YES NO NO NO YES
result:
ok 8 tokens
Test #2:
score: 0
Accepted
time: 23ms
memory: 8532kb
input:
1 2 6 2 1 1 1 1 1 200000 2 6 2 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 4 1 2 1 2 1 1 1 1 1 2 2 5 1 1 1 1 1 1 2 1 1 1 2 6 1 1 1 2 1 1 2 1 1 2 2 3 1 1 1 1 2 1 1 2 6 2 1 1 2 2 4 1 1 1 2 2 6 1 1 1 2 1 1 1 2 5 2 2 6 2 1 1 1 2 4 2 2 5 2 2 6 2 1 1 1 2 5 1 2 6 2 1 1 2 1 1 1 1 1 1 2 4 1 1 1 2 1 1 2 1 1 2 2 3 2...
output:
NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #3:
score: 0
Accepted
time: 26ms
memory: 8484kb
input:
6 2 1 1 2 1 2 1 1 200000 2 1 1 1 1 2 1 1 1 2 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 1 2 1 3 1 1 6 2 1 5 2 1 4 2 1 3 1 2 1 2 1 4 2 1 4 2 2 1 2 2 1 2 1 3 1 1 6 1 1 1 2 2 1 1 1 6 1 1 3 1 1 5 2 1 6 2 1 5 2 2 1 2 1 2 1 1 5 2 2 1 1 2 1 1 1 6 1 2 1 2 2 1 1 1 3 2 2 1 1 1 6 1 1 4 2 1 2 1 1 1 1 2 1 1 1 2 1 1 6 2 1 6 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #4:
score: 0
Accepted
time: 30ms
memory: 8456kb
input:
6 1 3 1 2 1 2 6 2 1 3 3 3 1 200000 2 4 2 1 2 1 1 6 2 2 3 2 1 1 1 1 6 2 1 6 2 1 3 2 2 6 1 2 4 3 1 1 2 2 5 2 2 6 2 2 3 1 1 4 3 1 3 1 2 5 2 2 4 2 2 1 3 1 1 1 2 2 2 2 4 2 1 5 3 1 6 3 2 6 3 1 5 3 2 5 3 2 4 1 2 4 2 1 1 2 1 6 1 2 6 1 1 2 3 1 1 3 1 1 1 2 6 3 2 4 1 1 4 2 2 2 1 1 3 1 1 1 3 1 1 3 1 4 3 1 3 3 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #5:
score: 0
Accepted
time: 25ms
memory: 8548kb
input:
4 1 1 2 2 1 1 200000 2 1 2 1 1 3 1 2 1 2 1 2 2 1 2 2 1 3 2 1 1 2 1 1 1 4 2 2 1 3 1 3 1 1 2 1 1 3 2 2 1 1 1 4 2 2 1 1 2 1 2 1 1 1 2 1 2 2 1 1 1 4 1 1 2 2 2 1 1 1 1 1 1 4 3 2 1 3 1 1 3 2 1 2 1 2 1 2 1 1 2 1 1 2 1 1 2 1 3 2 1 2 1 2 3 2 1 3 1 3 3 2 1 1 1 2 3 2 1 2 1 1 2 2 1 2 2 1 3 1 2 1 1 4 3 2 1 2 2 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #6:
score: 0
Accepted
time: 26ms
memory: 8544kb
input:
2 4 2 4 2 3 3 2 200000 1 1 2 1 2 2 1 2 2 1 2 4 1 1 2 1 2 4 2 2 1 1 1 3 2 3 2 2 3 1 2 2 4 2 3 2 2 2 1 1 1 4 1 2 4 2 2 1 1 1 2 2 1 2 2 4 4 1 2 4 1 2 3 2 4 4 2 3 1 2 1 3 2 3 1 2 2 1 1 1 2 2 2 1 1 2 3 1 2 2 1 2 1 1 2 4 1 2 4 1 1 3 1 1 4 2 1 3 1 1 1 1 2 4 2 1 2 2 3 4 1 2 4 2 2 1 1 2 1 2 3 2 1 2 3 2 3 3 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #7:
score: 0
Accepted
time: 22ms
memory: 8024kb
input:
7 3 3 4 1 1 3 3 5 3 3 2 1 4 200000 2 2 1 2 2 1 2 5 1 1 6 1 1 5 2 2 1 4 1 4 2 1 6 4 1 7 1 1 2 3 2 5 1 2 5 4 1 6 2 1 5 2 1 4 1 1 2 1 2 2 2 1 3 4 1 7 2 1 6 3 2 5 1 1 5 1 1 7 3 2 1 3 2 3 1 1 3 2 2 2 2 1 7 4 2 1 4 1 3 2 1 1 2 1 5 3 1 5 3 2 2 2 1 5 3 2 5 3 2 3 2 1 1 3 1 2 2 2 2 1 2 1 4 2 1 2 1 3 4 2 1 1 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #8:
score: 0
Accepted
time: 23ms
memory: 8536kb
input:
1 3 7 4 4 5 5 5 5 4 200000 2 2 4 2 6 4 1 1 4 2 6 4 2 1 3 2 2 3 2 1 3 1 1 5 1 1 5 2 3 5 1 1 4 1 1 4 2 6 5 2 5 1 2 1 2 2 7 2 1 1 5 2 4 5 1 1 2 1 1 3 2 4 2 2 1 3 1 1 3 2 1 1 1 1 1 2 3 1 1 1 4 1 1 5 1 1 1 2 5 2 2 7 3 1 1 5 2 6 4 1 1 4 2 7 4 2 3 3 2 3 1 1 1 3 1 1 3 2 4 4 1 1 4 1 1 2 1 1 1 2 3 1 2 1 1 1 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #9:
score: 0
Accepted
time: 21ms
memory: 8544kb
input:
8 3 1 2 2 1 4 4 4 3 1 4 4 200000 1 2 1 1 5 1 2 1 1 2 1 1 2 2 2 2 3 1 1 5 5 1 6 2 1 2 5 1 3 1 1 5 1 2 1 5 2 1 2 1 4 4 2 3 3 1 4 3 2 2 2 2 3 1 1 6 4 1 1 3 1 2 3 2 2 5 2 3 3 2 1 3 2 3 4 2 1 4 2 2 5 2 2 4 2 2 2 1 3 1 1 8 2 2 2 3 1 2 2 1 1 2 1 1 1 1 3 1 2 1 3 2 2 3 1 6 2 2 2 4 1 6 3 2 1 1 1 1 4 2 1 4 2 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #10:
score: 0
Accepted
time: 26ms
memory: 9796kb
input:
3 6 1 5 2 5 3 200000 1 2 4 1 1 3 1 2 5 2 2 5 1 3 3 1 1 6 1 3 1 1 2 1 2 1 6 2 1 4 2 1 2 2 2 3 1 3 1 1 3 5 1 2 4 2 2 5 1 2 5 1 3 1 2 1 3 1 2 6 1 2 4 2 1 3 1 2 4 1 2 1 1 3 2 2 2 6 2 1 4 2 2 4 1 1 2 1 1 4 2 2 2 2 1 4 1 2 2 1 1 3 2 1 4 1 3 3 2 1 6 2 2 2 1 1 6 1 3 6 1 2 2 1 3 1 2 2 3 1 2 2 2 1 2 2 2 5 2 2...
output:
NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #11:
score: 0
Accepted
time: 24ms
memory: 8476kb
input:
3 1 1 6 5 2 3 4 4 6 200000 2 3 5 2 5 5 1 1 4 1 2 4 1 1 1 2 4 3 2 1 2 1 1 6 2 2 2 2 5 4 1 3 4 1 3 4 2 3 5 2 1 6 1 1 1 2 3 4 2 3 5 2 2 5 1 1 5 1 2 2 1 3 2 2 2 1 1 3 5 2 3 6 1 3 3 2 1 3 2 5 3 1 1 1 2 4 4 2 5 1 2 2 5 1 2 2 1 2 3 2 4 5 1 3 5 2 1 1 2 5 1 1 2 1 2 5 4 2 3 1 2 1 6 1 1 2 1 3 6 1 2 1 2 3 6 1 1...
output:
YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #12:
score: 0
Accepted
time: 34ms
memory: 8604kb
input:
8 73198 31688 65092 21397 35031 58089 52944 16010 5 31090 97692 26708 44940 89767 200000 2 5 31191 1 1 60759 1 6 70508 1 2 97983 2 3 53563 1 4 22102 1 7 36211 1 3 33339 1 8 49224 1 7 82146 2 5 97668 1 4 13552 1 2 26414 2 4 3381 1 4 42198 1 4 28786 2 2 29892 2 2 77347 1 5 53766 2 5 55142 2 5 74266 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #13:
score: -100
Time Limit Exceeded
input:
100000 45952 97807 4941 35929 10776 28013 47912 21386 48030 55110 1347 96260 91732 78252 37717 2556 44017 67045 91588 59689 86623 88384 41158 38652 77627 83554 48557 85544 94827 54704 86949 61451 79790 92480 74798 43911 65450 20096 17129 95952 87522 98877 41827 51143 42419 98384 27210 34607 91233 46...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...