QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696248 | #8338. Quad Kingdoms Chess | Legend_dy | WA | 30ms | 5412kb | C++20 | 2.6kb | 2024-10-31 21:56:34 | 2024-10-31 21:56:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
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;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5116kb
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: 22ms
memory: 5412kb
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: 23ms
memory: 5220kb
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: 30ms
memory: 5192kb
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'