QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353838 | #8338. Quad Kingdoms Chess | ucup-team2681 | WA | 34ms | 16120kb | C++23 | 2.1kb | 2024-03-14 17:26:21 | 2024-03-14 17:26:23 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int a[100005],b[100005],qp[100005];
const int p=998244353,seed=233;
struct node{
int hsh,cnt;
};
node operator+(node a,node b){
return (node){(int)(((ll)a.hsh*qp[b.cnt]+b.hsh)%p),a.cnt+b.cnt};
};
struct sgtree{
int mx[100005<<2],mn[100005<<2];
node tree[100005<<2];
node find(int u,int l,int r,int qmn){
if(mn[u]>=qmn)return tree[u];
if(mx[u]<qmn)return{0,0};
return find(u<<1,l,l+r>>1,qmn)+find(u<<1|1,l+r+2>>1,r,qmn);
}
void push_up(int u,int l,int r){
mx[u]=max(mx[u<<1],mx[u<<1|1]);
mn[u]=mn[u<<1|1];
tree[u]=find(u<<1,l,l+r>>1,mx[u<<1|1])+tree[u<<1|1];
}
void upd(int u,int l,int r,int k,int x){
if(l==r){
mx[u]=mn[u]=x;
tree[u]={x,1};
return;
}
if(k<=(l+r>>1))upd(u<<1,l,l+r>>1,k,x);
else upd(u<<1|1,l+r+2>>1,r,k,x);
push_up(u,l,r);
}
void build(int u,int l,int r,int a[]){
if(l==r){
mx[u]=mn[u]=a[l];
tree[u]={a[l],1};
return;
}
build(u<<1,l,l+r>>1,a);
build(u<<1|1,l+r+2>>1,r,a);
push_up(u,l,r);
}
int hash(){
return tree[1].hsh;
}
}t1,t2;
void solve(){
int n1,n2;
scanf("%d",&n1);
for(int i=1;i<=n1;i++){
scanf("%d",&a[i]);
}
scanf("%d",&n2);
for(int i=1;i<=n2;i++){
scanf("%d",&b[i]);
}
t1.build(1,1,n1,a);
puts("");
t2.build(1,1,n2,b);
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
int t,k,x;
scanf("%d%d%d",&t,&k,&x);
if(t==1){
t1.upd(1,1,n1,k,x);
}
else{
t2.upd(1,1,n2,k,x);
}
if(t1.hash()==t2.hash()){
puts("YES");
}
else{
puts("NO");
}
}
}
int main(){
qp[0]=1;
for(int i=1;i<=1e5;i++){
qp[i]=(ll)qp[i-1]*seed%p;
}
int t=1;
//scanf("%d",&t);
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10300kb
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: 26ms
memory: 14332kb
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 ...
result:
ok 200000 tokens
Test #3:
score: 0
Accepted
time: 25ms
memory: 14408kb
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: 0
Accepted
time: 34ms
memory: 11968kb
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 ...
result:
ok 200000 tokens
Test #5:
score: 0
Accepted
time: 24ms
memory: 16120kb
input:
4 1 1 2 2 1 1 200000 2 1 2 1 1 3 1 2 1 2 1 2 2 1 2 2 1 3 2 1 1 2 1 1 1 4 2 2 1 3 1 3 1 1 2 1 1 3 2 2 1 1 1 4 2 2 1 1 2 1 2 1 1 1 2 1 2 2 1 1 1 4 1 1 2 2 2 1 1 1 1 1 1 4 3 2 1 3 1 1 3 2 1 2 1 2 1 2 1 1 2 1 1 2 1 1 2 1 3 2 1 2 1 2 3 2 1 3 1 3 3 2 1 1 1 2 3 2 1 2 1 1 2 2 1 2 2 1 3 1 2 1 1 4 3 2 1 2 2 1...
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 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 YES NO NO NO NO YES NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #6:
score: 0
Accepted
time: 25ms
memory: 10264kb
input:
2 4 2 4 2 3 3 2 200000 1 1 2 1 2 2 1 2 2 1 2 4 1 1 2 1 2 4 2 2 1 1 1 3 2 3 2 2 3 1 2 2 4 2 3 2 2 2 1 1 1 4 1 2 4 2 2 1 1 1 2 2 1 2 2 4 4 1 2 4 1 2 3 2 4 4 2 3 1 2 1 3 2 3 1 2 2 1 1 1 2 2 2 1 1 2 3 1 2 2 1 2 1 1 2 4 1 2 4 1 1 3 1 1 4 2 1 3 1 1 1 1 2 4 2 1 2 2 3 4 1 2 4 2 2 1 1 2 1 2 3 2 1 2 3 2 3 3 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES YES 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 NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #7:
score: -100
Wrong Answer
time: 29ms
memory: 10312kb
input:
7 3 3 4 1 1 3 3 5 3 3 2 1 4 200000 2 2 1 2 2 1 2 5 1 1 6 1 1 5 2 2 1 4 1 4 2 1 6 4 1 7 1 1 2 3 2 5 1 2 5 4 1 6 2 1 5 2 1 4 1 1 2 1 2 2 2 1 3 4 1 7 2 1 6 3 2 5 1 1 5 1 1 7 3 2 1 3 2 3 1 1 3 2 2 2 2 1 7 4 2 1 4 1 3 2 1 1 2 1 5 3 1 5 3 2 2 2 1 5 3 2 5 3 2 3 2 1 1 3 1 2 2 2 2 1 2 1 4 2 1 2 1 3 4 2 1 1 1...
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 YES NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
wrong answer 1889th words differ - expected: 'YES', found: 'NO'