QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534463#8338. Quad Kingdoms Chesstraining_233WA 6ms18560kbC++142.2kb2024-08-27 10:50:332024-08-27 10:50:33

Judging History

你现在查看的是最新测评结果

  • [2024-08-27 10:50:33]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:18560kb
  • [2024-08-27 10:50:33]
  • 提交

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'