QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696224 | #8338. Quad Kingdoms Chess | Legend_dy | WA | 31ms | 5408kb | C++20 | 2.6kb | 2024-10-31 21:52:48 | 2024-10-31 21:52:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 9;
constexpr int base = 133331;
void inc(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int add(int x, int y) {
inc(x, y);
return x;
}
int mul(int x, int y) {
return 1ll * x * y % mod;
}
int qpow(int x, int n) {
int y = 1;
for (; n; n /= 2, x = mul(x, x)) if (n & 1) y = mul(y, x);
return y;
}
struct node {
int cnt = 0;
int max = 0;
int hash = 0;
};
constexpr int MAXN = 2e5 + 5;
int pw[MAXN], inv_pw[MAXN];
#define ls (u << 1)
#define rs (u << 1 | 1)
struct segtree {
vector<node> tr;
segtree(int n) : tr(n << 2) {}
node Add(const node &L, const node &R) {
node c;
c.cnt = L.cnt + R.cnt;
c.hash = (1ll * L.hash * pw[R.cnt] + R.hash) % mod;
return c;
}
node Del(const node &L, const node &R) {
node c;
c.cnt = L.cnt - R.cnt;
c.hash = 1ll * add(L.hash, mod - R.hash) * inv_pw[R.cnt] % mod;
return c;
}
node get(int x, int l, int r, int u) {
if (tr[u].max < x) return {};
if (l == r) return tr[u];
int m = l + r >> 1;
if (tr[rs].max < x) return get(x, l, m, ls);
else return Add(get(x, m + 1, r, rs), Del(tr[u], tr[rs]));
}
void modify(int x, int v, int l, int r, int u) {
if (l == r) {
tr[u] = {1, v, v};
return;
}
int m = l + r >> 1;
if (x <= m) modify(x, v, l, m, ls);
else modify(x, v, m + 1, r, rs);
tr[u] = Add(get(tr[rs].max, l, m, ls), tr[rs]);
tr[u].max = std::max(tr[ls].max, tr[rs].max);
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int inv_base = qpow(base, mod - 2);
inv_pw[0] = 1;
pw[0] = 1;
for (int i = 1; i < MAXN; i++) {
pw[i] = mul(pw[i - 1], base);
inv_pw[i] = mul(inv_pw[i - 1], inv_base);
}
int n1;
cin >> n1;
segtree st1(n1);
for (int i = 1, x; i <= n1; i++) {
cin >> x;
st1.modify(i, x, 1, n1, 1);
}
int n2;
cin >> n2;
segtree st2(n2);
for (int i = 1, x; i <= n2; i++) {
cin >> x;
st2.modify(i, x, 1, n2, 1);
}
int Q;
cin >> Q;
while (Q--) {
int o, x, y;
cin >> o >> x >> y;
if (o == 1) {
st1.modify(x, y, 1, n1, 1);
}else {
st2.modify(x, y, 1, n2, 1);
}
cout << (st1.tr[1].hash == st2.tr[1].hash ? "YES\n" : "NO\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5408kb
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: 27ms
memory: 5348kb
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: 27ms
memory: 5128kb
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: -100
Wrong Answer
time: 31ms
memory: 5128kb
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:
wrong answer 281st words differ - expected: 'YES', found: 'NO'