QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694379 | #8338. Quad Kingdoms Chess | snow_mikumiku | WA | 1ms | 8528kb | C++14 | 3.1kb | 2024-10-31 17:49:28 | 2024-10-31 17:49:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UL = unsigned long long;
const UL mi = 995329;
const int N = 1e5 + 10;
UL m995[N], a[N], b[N];
struct tree {
UL max, hs;
}A[N << 2], B[N << 2];
UL ask(int p, UL mx, int ty, int l, int r)
{
int mid = l + r >> 1;
if(!ty) {
if(A[p].max < mx) return 0;
if(l == r) return A[p].hs;
if(A[p * 2].max < mx)
return ask(p * 2 + 1, mx, ty, mid + 1, r);
else
return A[p].hs - A[p * 2].hs + ask(p * 2, mx, ty, l, mid);
}
else {
if(B[p].max < mx) return 0;
if(l == r) return B[p].hs;
if(B[p * 2].max < mx)
return ask(p * 2 + 1, mx, ty, mid + 1, r);
else
return B[p].hs - B[p * 2].hs + ask(p * 2, mx, ty, l, mid);
}
}
void build(int p, int l, int r, int ty)
{
if(!ty) {
if(l == r) {
A[p].hs = m995[a[l]];
A[p].max = a[l];
return;
}
int mid = l + r >> 1;
build(p * 2, l, mid, 0);
build(p * 2 + 1, mid + 1, r, 0);
A[p].max = max(A[p * 2].max, A[p * 2 + 1].max);
A[p].hs = A[p * 2].hs + ask(p * 2 + 1, A[p * 2].max, 1, mid + 1, r);
}
else {
if(l == r) {
B[p].hs = m995[b[l]];
B[p].max = b[l];
return;
}
int mid = l + r >> 1;
build(p * 2, l, mid, 1);
build(p * 2 + 1, mid + 1, r, 1);
B[p].max = max(B[p * 2].max, B[p * 2 + 1].max);
B[p].hs = B[p * 2].hs + ask(p * 2 + 1, B[p * 2].max, 1, mid + 1, r);
}
}
void change(int x, int p, UL To, int ty, int l, int r)
{
if(!ty) {
if(l == r) {
A[p].hs = m995[To] * To;
A[p].max = To;
return;
}
int mid = l + r >> 1;
if(x <= mid) change(x, p * 2, To, ty, l, mid);
else change(x, p * 2 + 1, To, ty, mid + 1, r);
A[p].max = max(A[p * 2].max, A[p * 2 + 1].max);
A[p].hs = A[p * 2].hs + ask(p * 2 + 1, A[p * 2].max, 1, mid + 1, r);
}
else {
if(l == r) {
B[p].hs = m995[To] * To;
B[p].max = To;
return;
}
int mid = l + r >> 1;
if(x <= mid) change(x, p * 2, To, ty, l, mid);
else change(x, p * 2 + 1, To, ty, mid + 1, r);
B[p].max = max(B[p * 2].max, B[p * 2 + 1].max);
B[p].hs = B[p * 2].hs + ask(p * 2 + 1, B[p * 2].max, 1, mid + 1, r);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
m995[0] = 1;
for(int i = 1; i < N; i++) m995[i] = m995[i - 1] * mi;
int n, m, q;
cin >> n;
for(int i = n; i >= 1; i--) cin >> a[i];
cin >> m;
for(int i = m; i >= 1; i--) cin >> b[i];
build(1, 1, n, 0);
build(1, 1, m, 1);
int op, x, y;
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> op >> x >> y;
if(op == 1) x = n - x + 1, change(x, 1, y, 0, 1, n);
if(op == 2) x = m - x + 1, change(x, 1, y, 1, 1, m);
if(B[1].hs == A[1].hs) cout << "YES\n";
else cout << "NO\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 8528kb
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'