QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534463 | #8338. Quad Kingdoms Chess | training_233 | WA | 6ms | 18560kb | C++14 | 2.2kb | 2024-08-27 10:50:33 | 2024-08-27 10:50:33 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,p1=998244353,p2=1,base=114514123;
struct node{
int len,h1,h2;
bool operator == (const node &x) const{
return len==x.len&&h1==x.h1&&h2==x.h2;
}
};
int n1,n2,q;
int pw1[N],pw2[N];
int a1[N],a2[N];
struct Tree{
#define ls (k<<1)
#define rs (k<<1|1)
int mx[N<<2],len[N<<2];
node H[N<<2];
node calc(int k,int l,int r,int pre){
if(l==r)return (node){mx[k]>=pre,mx[k]>=pre?mx[k]:0,mx[k]>=pre?mx[k]:0};
int m=l+r>>1;
if(mx[ls]<pre)return calc(rs,m+1,r,pre);
else{
node o=calc(ls,l,m,pre),ret;
ret.len=o.len+len[k]-len[ls];
ret.h1=(o.h1*pw1[len[k]-len[ls]]+H[k].h1-H[ls].h1*pw1[len[k]-len[ls]]%p1+p1)%p1;
ret.h2=(o.h2*pw2[len[k]-len[ls]]+H[k].h2-H[ls].h2*pw2[len[k]-len[ls]]%p2+p2)%p2;
return ret;
}
}
void up(int k,int l,int r){
int m=l+r>>1;
mx[k]=max(mx[ls],mx[rs]);
node o=calc(rs,m+1,r,mx[ls]);
len[k]=len[ls]+o.len;
H[k].h1=(H[ls].h1*pw1[o.len]+o.h1)%p1;
H[k].h2=(H[ls].h2*pw2[o.len]+o.h2)%p2;
}
void build(int k,int l,int r,int* a){
if(l==r)return mx[k]=H[k].h1=H[k].h2=a[l],len[k]=1,void();
int m=l+r>>1;
build(ls,l,m,a),build(rs,m+1,r,a);
up(k,l,r);
}
void mdf(int k,int l,int r,int x,int v){
if(l==r)return mx[k]=v,H[k].h1=H[k].h2=v,void();
int m=l+r>>1;
x<=m?mdf(ls,l,m,x,v):mdf(rs,m+1,r,x,v);
up(k,l,r);
}
}T1,T2;
signed main(){
pw1[0]=pw2[0]=1;
For(i,1,N-1)
pw1[i]=pw1[i-1]*base%p1,
pw2[i]=pw2[i-1]*base%p2;
For(i,1,n1=read())a1[i]=read();
reverse(a1+1,a1+1+n1);
T1.build(1,1,n1,a1);
For(i,1,n2=read())a2[i]=read();
reverse(a2+1,a2+1+n2);
T2.build(1,1,n2,a2);
q=read();
while(q--){
int op=read(),x=read(),y=read();
if(op==1)T1.mdf(1,1,n1,n1-x+1,y);
else T2.mdf(1,1,n2,n2-x+1,y);
puts(T1.H[1]==T2.H[1]?"YES":"NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 18560kb
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: -100
Wrong Answer
time: 6ms
memory: 17572kb
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 NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO 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 5th words differ - expected: 'YES', found: 'NO'