QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
詳細信息
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'