QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547335 | #8338. Quad Kingdoms Chess | light_ink_dots# | WA | 30ms | 16712kb | C++20 | 1.6kb | 2024-09-04 20:36:34 | 2024-09-04 20:36:35 |
Judging History
answer
//最接近夜的灰褪去的那抹苍蓝
#include<bits/stdc++.h>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define mid (l+r>>1)
using namespace std;
const int maxn=100005,maxt=maxn<<2;
int n1,n2,m,T,ans,flg;
int a1[maxn],a2[maxn],mx[2][maxt];
unsigned long long res[2][maxt],rec[2][maxt],R[maxn];
mt19937_64 rnd(time(0));
int find(int l,int r,int now,int V,int typ){
if(l==r)
return mx[typ][now]>=V? R[mx[typ][now]]:0;
if(mx[typ][rc(now)]>=V)
return rec[typ][now]+find(mid+1,r,rc(now),V,typ);
return find(l,mid,lc(now),V,typ);
}
void pushup(int l,int r,int now,int typ){
mx[typ][now]=max(mx[typ][lc(now)],mx[typ][rc(now)]);
rec[typ][now]=find(l,mid,lc(now),mx[typ][rc(now)],typ);
res[typ][now]=res[typ][rc(now)]+rec[typ][now];
}
void build(int l,int r,int now,int typ){
if(l==r){
mx[typ][now]=(typ==0? a1:a2)[l],res[typ][now]=R[mx[typ][now]];
return ;
}
build(l,mid,lc(now),typ),build(mid+1,r,rc(now),typ),pushup(l,r,now,typ);
}
void modify(int l,int r,int now,int p,int typ,int v){
if(l==r){
mx[typ][now]=v,res[typ][now]=R[v];
return ;
}
if(p<=mid)
modify(l,mid,lc(now),p,typ,v);
else modify(mid+1,r,rc(now),p,typ,v);
pushup(l,r,now,typ);
}
int main(){
for(int i=0;i<maxn;i++)
R[i]=rnd();
scanf("%d",&n1);
for(int i=1;i<=n1;i++)
scanf("%d",&a1[i]);
scanf("%d",&n2);
for(int i=1;i<=n2;i++)
scanf("%d",&a2[i]);
build(1,n1,1,0),build(1,n2,1,1);
scanf("%d",&m);
for(int i=1,o,x,y;i<=m;i++){
scanf("%d%d%d",&o,&x,&y);
if(o==1)
a1[x]=y,modify(1,n1,1,x,0,y);
if(o==2)
a2[x]=y,modify(1,n2,1,x,1,y);
puts(res[0][1]==res[1][1]? "YES":"NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14916kb
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: 16620kb
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: 25ms
memory: 12792kb
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: 30ms
memory: 16712kb
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 NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO 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:
wrong answer 27th words differ - expected: 'YES', found: 'NO'