QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473128 | #8338. Quad Kingdoms Chess | chengning0909 | WA | 1ms | 8016kb | C++14 | 3.0kb | 2024-07-11 22:09:28 | 2024-07-11 22:09:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rnd;
const int N = 1e5 + 10, mod = 1e9 + 7;
struct Node {
ll h, past;
int mmax;
} tr[2][4 * N];
int n, a[N], m, b[N], q;
ll to[N];
void Back(int i, int k) {
tr[k][i].h = (tr[k][i].h - tr[k][i].past + mod) % mod;
tr[k][i].past = 0;
}
void update(int i, int l, int r, ll k, int p) {
tr[p][i].h = (tr[p][i].h + k) % mod;
tr[p][i].past = (tr[p][i].past + k) % mod;
}
void pushdown(int i, int l, int mid, int r, int p) {
update(i * 2, l, mid, tr[p][i].h, p);
update(i * 2 + 1, mid + 1, r, tr[p][i].h, p);
tr[p][i].h = 0;
}
Node getans(int i, int l, int r, int x, int k) {
if (l == r) return tr[k][i];
int mid = (l + r) >> 1;
pushdown(i, l, mid, r, k);
return tr[k][i * 2 + 1].mmax >= x ? getans(i * 2 + 1, mid + 1, r, x, k) : getans(i * 2, l, mid, x, k);
}
void Modify(int i, int l, int r, int p, int x, int k) {
if (l == r) {
tr[k][i] = {to[x], 0, x};
return ;
}
int mid = (l + r) >> 1;
pushdown(i, l, mid, r, k);
p <= mid ? Modify(i * 2, l, mid, p, x, k) : Modify(i * 2 + 1, mid + 1, r, p, x, k);
tr[k][i].mmax = max(tr[k][i * 2].mmax, tr[k][i * 2 + 1].mmax);
}
void modify(int i, int l, int r, int p, int k) {
if (l == r) return ;
int mid = (l + r) >> 1;
pushdown(i, l, mid, r, k);
Back(i * 2 + 1, k);
p <= mid ? modify(i * 2, l, mid, p, k) : modify(i * 2 + 1, mid + 1, r, p, k);
int mmax = tr[k][i * 2 + 1].mmax;
Node tmp = getans(i * 2, l, mid, mmax, k);
if (tmp.mmax >= mmax) update(i * 2 + 1, mid + 1, r, tmp.h, k);
}
Node build(int i, int l, int r, int k) {
if (l == r) return tr[k][i] = (!k ? Node{to[a[l]], 0, a[l]} : Node{to[b[l]], 0, b[l]});
int mid = (l + r) >> 1;
build(i * 2, l, mid, k), build(i * 2 + 1, mid + 1, r, k);
int mmax = tr[k][i * 2 + 1].mmax;
Node tmp = getans(i * 2, l, mid, mmax, k);
if (tmp.mmax >= mmax) update(i * 2 + 1, mid + 1, r, tmp.h, k);
tr[k][i].mmax = max(tr[k][i * 2].mmax, tr[k][i * 2 + 1].mmax);
return tr[k][i];
}
ll query(int i, int l, int r, int pos, int k) {
if (l == r) return tr[k][i].h;
int mid = (l + r) >> 1;
pushdown(i, l, mid, r, k);
return pos <= mid ? query(i * 2, l, mid, pos, k) : query(i * 2 + 1, mid + 1, r, pos, k);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
rnd = mt19937(time(0));
for (int i = 1; i <= 1e5; i++) to[i] = rnd() % mod;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i];
build(1, 1, n, 0), build(1, 1, m, 1);
cin >> q;
while (q--) {
int op, pos, v; cin >> op >> pos >> v;
if (op == 1) Modify(1, 1, n, pos, v, 0), modify(1, 1, n, pos, 0);
else Modify(1, 1, m, pos, v, 1), modify(1, 1, m, pos, 1);
cout << (query(1, 1, n, n, 0) == query(1, 1, m, m, 1) ? "YES\n" : "NO\n");
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 8016kb
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 NO NO NO NO YES
result:
wrong answer 4th words differ - expected: 'YES', found: 'NO'