QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468862 | #8338. Quad Kingdoms Chess | real_sigma_team | WA | 58ms | 80480kb | C++20 | 5.8kb | 2024-07-09 02:04:44 | 2024-07-09 02:04:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
void solve();
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
mt19937_64 mt(time(nullptr));
const int N = 100100, K = 2, mod = 100'000'007;
int a[N], b[N], prv[mod], sufa[N], sufb[N], prva[N], suffa[N], prvb[N], suffb[N], mna[N], mnb[N], inda[N], indb[N];
unsigned long long hsh[N], prefa[N], prefb[N];
pair<int, int> cha[N], chb[N], stk[2 * N], chas[N], chbs[N];
pair<int, pair<int, int>> que[2 * N], chall[N];
void solve() {
for (int i = 0; i < N; i++) {
hsh[i] = mt();
}
int n1, n2, q, a0;
cin >> n1;
for (int i = 0; i < n1; i++) {
cin >> a[i];
}
a0 = a[0];
cin >> n2;
for (int i = 0; i < n2; i++) {
cin >> b[i];
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> que[i].x >> que[i].y.x >> que[i].y.y; que[i].y.x--;
}
for (int st = 0; st < q; st += K) {
int sz = min(K, q - st);
for (int i = 0; i < n1; i++) {
mna[i] = a[i];
}
for (int i = 0; i < n2; i++) {
mnb[i] = b[i];
}
int indasz = 0, indbsz = 0;
set<int> ia, ib;
for (int i = 0; i < sz; i++) {
chall[i] = que[i + st];
if (chall[i].x == 1) {
mna[chall[i].y.x] = min(mna[chall[i].y.x], chall[i].y.y);
ia.insert(chall[i].y.x);
} else {
mnb[chall[i].y.x] = min(mnb[chall[i].y.x], chall[i].y.y);
ib.insert(chall[i].y.x);
}
}
for (int i : ia) {
inda[indasz++] = i;
}
for (int i : ib) {
indb[indbsz++] = i;
}
{
sufa[n1 - 1] = 0;
for (int i = n1 - 2; i >= 0; i--) {
sufa[i] = max(sufa[i + 1], mna[i + 1]);
}
prefa[0] = 0;
for (int i = 0; i < n1; i++) {
if (mna[i] >= sufa[i]) {
prefa[i + 1] = prefa[i] + hsh[mna[i]];
} else {
prefa[i + 1] = prefa[i];
}
}
int chassz = 0;
for (int i = 0; i < sz; i++) {
if (chall[i].x == 1) {
chas[chassz++] = chall[i].y;
chas[chassz++] = {chall[i].y.x, a[chall[i].y.x]};
}
}
sort(chas, chas + chassz);
int stksz = 1, ptr = 0;
stk[0] = {INT32_MAX, -1};
for (int i = 0; i < n1; i++) {
while (mna[i] > stk[stksz - 1].x) {
stksz--;
}
while (ptr < chassz && chas[ptr].x == i) {
int nw = stksz;
for (int l = 17; l >= 0; l--) {
if (nw - (1 << l) >= 0 && stk[nw - (1 << l)].x < chas[ptr].y) {
nw -= (1 << l);
}
}
nw--;
prv[(hsh[chas[ptr].x] + hsh[31] * hsh[chas[ptr].y] + hsh[2]) % mod] = stk[nw].y;
ptr++;
}
stk[stksz++] = {mna[i], i};
}
}
{
sufb[n2 - 1] = 0;
for (int i = n2 - 2; i >= 0; i--) {
sufb[i] = max(sufb[i + 1], mnb[i + 1]);
}
prefb[0] = 0;
for (int i = 0; i < n2; i++) {
if (mnb[i] >= sufb[i]) {
prefb[i + 1] = prefb[i] + hsh[mnb[i]];
} else {
prefb[i + 1] = prefb[i];
}
}
int chbssz = 0;
for (int i = 0; i < sz; i++) {
if (chall[i].x == 2) {
chbs[chbssz++] = chall[i].y;
chbs[chbssz++] = {chall[i].y.x, b[chall[i].y.x]};
}
}
sort(chbs, chbs + chbssz);
int stksz = 1, ptr = 0;
stk[0] = {INT32_MAX, -1};
for (int i = 0; i < n2; i++) {
while (mnb[i] > stk[stksz - 1].x) {
stksz--;
}
while (ptr < chbssz && chbs[ptr].x == i) {
int nw = stksz;
for (int l = 17; l >= 0; l--) {
if (nw - (1 << l) >= 0 && stk[nw - (1 << l)].x < chbs[ptr].y) {
nw -= (1 << l);
}
}
nw--;
prv[(hsh[chbs[ptr].x] + hsh[31] * hsh[chbs[ptr].y] + hsh[1]) % mod] = stk[nw].y;
ptr++;
}
stk[stksz++] = {mnb[i], i};
}
}
unsigned long long resmna = prefa[n1], resmnb = prefb[n2];
for (int c = 0; c < sz; c++) {
int chasz = 0, chbsz = 0;
unsigned long long resa = resmna, resb = resmnb;
if (chall[c].x == 1) {
a[chall[c].y.x] = chall[c].y.y;
} else {
b[chall[c].y.x] = chall[c].y.y;
}
{
for (int i = 0; i < indasz; i++) {
if (mna[inda[i]] != a[inda[i]]) {
cha[chasz++] = {inda[i], a[inda[i]]};
}
}
int stksz = 1;
stk[0] = {INT32_MAX, -1};
for (int i = 0; i < chasz; i++) {
while (cha[i].y > stk[stksz - 1].x) {
stksz--;
}
prva[i] = stk[stksz - 1].y;
stk[stksz++] = {cha[i].y, cha[i].x};
}
suffa[chasz - 1] = 0;
for (int i = chasz - 2; i >= 0; i--) {
suffa[i] = max(suffa[i + 1], cha[i + 1].y);
}
for (int i = 0; i < chasz; i++) {
if (max(suffa[i], sufa[cha[i].x]) > cha[i].y) {
continue;
}
int r = cha[i].x + 1;
int l;
int c1 = prva[i];
int c2 = prv[(hsh[cha[i].x] + hsh[31] * hsh[cha[i].y] + hsh[2]) % mod];
// int c2 = cha[i].x;
if (a[c1] > a[c2]) {
l = c1 + 1;
} else if (a[c2] > a[c1]) {
l = c2 + 1;
} else {
l = max(c1, c2) + 1;
}
resa -= prefa[r] - prefa[l];
resa += hsh[cha[i].y];
}
}
{
for (int i = 0; i < indbsz; i++) {
if (mnb[indb[i]] != b[indb[i]]) {
chb[chbsz++] = {indb[i], b[indb[i]]};
}
}
int stksz = 1;
stk[0] = {INT32_MAX, -1};
for (int i = 0; i < chbsz; i++) {
while (chb[i].y > stk[stksz - 1].x) {
stksz--;
}
prvb[i] = stk[stksz - 1].y;
stk[stksz++] = {chb[i].y, chb[i].x};
}
suffb[chbsz - 1] = 0;
for (int i = chbsz - 2; i >= 0; i--) {
suffb[i] = max(suffb[i + 1], chb[i + 1].y);
}
for (int i = 0; i < chbsz; i++) {
if (max(suffb[i], sufb[chb[i].x]) > chb[i].y) {
continue;
}
int r = chb[i].x + 1;
int l;
int c1 = prvb[i];
int c2 = prv[(hsh[chb[i].x] + hsh[31] * hsh[chb[i].y] + hsh[1]) % mod];
// int c2 = chb[i].x;
if (b[c1] > b[c2]) {
l = c1 + 1;
} else if (b[c2] > b[c1]) {
l = c2 + 1;
} else {
l = max(c1, c2) + 1;
}
resb -= prefb[r] - prefb[l];
resb += hsh[chb[i].y];
}
}
cout << (resa == resb ? "YES\n" : "NO\n");
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 48884kb
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: 44ms
memory: 44792kb
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: 45ms
memory: 46784kb
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: 58ms
memory: 80480kb
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 3352nd words differ - expected: 'NO', found: 'YES'