QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734936 | #8338. Quad Kingdoms Chess | warner1129 | WA | 25ms | 4752kb | C++14 | 1.5kb | 2024-11-11 16:08:02 | 2024-11-11 16:08:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
mt19937 rng(time(0));
constexpr u64 P = 1E9 + 321;
constexpr int kC = 1E5;
u64 pw[kC + 1];
struct Seg {
Seg *ls{}, *rs{};
int l, r;
int ma, mi;
u64 h{};
u64 get(int x) {
if (ma < x) {
return 0;
}
if (mi >= x) {
return h;
}
return ls->get(x) + rs->get(x);
}
void pull() {
ma = max(ls->ma, rs->ma);
mi = min(ls->mi, rs->mi);
h = ls->get(rs->ma) + rs->h;
}
Seg(int _l, int _r, const vector<int> &v) : l(_l), r(_r) {
if (r - l == 1) {
ma = mi = v[l];
h = pw[v[l]];
return;
}
int m = (l + r) / 2;
ls = new Seg(l, m, v);
rs = new Seg(m, r, v);
pull();
}
void set(int p, int v) {
if (r - l == 1) {
h = pw[v];
ma = mi = v;
return;
}
int m = (l + r) / 2;
if (p < m) {
ls->set(p, v);
} else {
rs->set(p, v);
}
pull();
}
};
void solve() {
vector<int> tmp;
int n;
cin >> n;
tmp.resize(n);
for (int &x : tmp) {
cin >> x;
}
Seg A(0, n, tmp);
int m;
cin >> m;
tmp.resize(m);
for (int &x : tmp) {
cin >> x;
}
Seg B(0, m, tmp);
int q;
cin >> q;
while (q--) {
int o, p, v;
cin >> o >> p >> v;
p--;
(o == 1 ? A : B).set(p, v);
if (A.get(-1) == B.get(-1)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
pw[0] = 1;
for (int i = 1; i <= kC; i++) {
pw[i] = pw[i - 1] * P;
}
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4424kb
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: 25ms
memory: 4752kb
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: 20ms
memory: 4560kb
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: 25ms
memory: 4432kb
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 1061st words differ - expected: 'YES', found: 'NO'