QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734972 | #8338. Quad Kingdoms Chess | warner1129 | WA | 1ms | 4356kb | C++20 | 1.6kb | 2024-11-11 16:21:04 | 2024-11-11 16:21:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
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{}, lh{};
u64 get(int x) {
if (ma < x) {
return 0;
}
if (mi >= x) {
return h;
}
if (x >= rs->ma) {
return ls->get(x) + rs->h;
}
return lh + rs->get(x);
}
void pull() {
ma = max(ls->ma, rs->ma);
mi = min(ls->mi, rs->mi);
lh = ls->get(rs->ma);
h = lh + 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: 0
Wrong Answer
time: 1ms
memory: 4356kb
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 NO
result:
wrong answer 8th words differ - expected: 'YES', found: 'NO'