QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#831823	#9774. Same Sum	tiphareth	WA	438ms	53240kb	C++14	4.4kb	2024-12-25 17:10:35	2024-12-25 17:10:35

Judging History

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

[2025-01-11 11:59:18]
hack成功，自动添加数据
(/hack/1443)

[2024-12-25 17:10:35]
评测

测评结果：WA
用时：438ms
内存：53240kb

查看

[2024-12-25 17:10:35]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int M=998244353,X=303331;
const int M2=1e9+7,Y=3333331;
const int M3=1e9+9,Z=250003;
ll tag[N<<2],s0[N<<2];
struct node{
	ll s;
	int x,y,z,w,a,b;
};
int s1[N<<2],s2[N<<2],n,q,a[N],v,i,op,x,y,XX,tag1[N<<2],tag2[N<<2];
int s3[N<<2],s4[N<<2],YY,tag3[N<<2],tag4[N<<2];
int s5[N<<2],s6[N<<2],ZZ,tag5[N<<2],tag6[N<<2];
int pw(int x,ll y,int M){
	int z=1;
	for (;y;y>>=1,x=1ll*x*x%M);
		if (y&1) z=1ll*z*x%M;
	return z;
}
int sum(int x,int y,int M){
	x+=y;if(x>=M)x-=M;
	return x;
}
void mul(int &x,int y,int M){x=1ll*x*y%M;}
void build(int t,int l,int r){
	tag[t]=0;
	tag1[t]=tag2[t]=tag3[t]=tag4[t]=tag5[t]=tag6[t]=1;
	if (l==r){
		s0[t]=a[l];
		s1[t]=pw(X,a[l],M);
		s2[t]=pw(XX,a[l],M);
		s3[t]=pw(Y,a[l],M2);
		s4[t]=pw(YY,a[l],M2);
		s5[t]=pw(Z,a[l],M3);
		s6[t]=pw(ZZ,a[l],M3);
		return;
	}
	int mid=(l+r)>>1;
	build(t<<1,l,mid);
	build(t<<1|1,mid+1,r);
	s0[t]=s0[t<<1]+s0[t<<1|1];
	s1[t]=sum(s1[t<<1],s1[t<<1|1],M);
	s2[t]=sum(s2[t<<1],s2[t<<1|1],M);
	s3[t]=sum(s3[t<<1],s3[t<<1|1],M2);
	s4[t]=sum(s4[t<<1],s4[t<<1|1],M2);
	s5[t]=sum(s5[t<<1],s5[t<<1|1],M3);
	s6[t]=sum(s6[t<<1],s6[t<<1|1],M3);
}
void down(int t,int l,int r){
	if (tag[t]){
		int mid=(l+r)>>1;
		tag[t<<1]+=tag[t],tag[t<<1|1]+=tag[t];
		mul(tag1[t<<1],tag1[t],M);
		mul(tag1[t<<1|1],tag1[t],M);
		mul(tag2[t<<1],tag2[t],M);
		mul(tag2[t<<1|1],tag2[t],M);
		mul(tag3[t<<1],tag3[t],M2);
		mul(tag3[t<<1|1],tag3[t],M2);
		mul(tag4[t<<1],tag4[t],M2);
		mul(tag4[t<<1|1],tag4[t],M2);
		mul(tag5[t<<1],tag5[t],M3);
		mul(tag5[t<<1|1],tag5[t],M3);
		mul(tag6[t<<1],tag6[t],M3);
		mul(tag6[t<<1|1],tag6[t],M3);
		s0[t<<1]+=(mid-l+1)*tag[t];
		s0[t<<1|1]+=(r-mid)*tag[t];
		mul(s1[t<<1],tag1[t],M);
		mul(s1[t<<1|1],tag1[t],M);
		mul(s2[t<<1],tag2[t],M);
		mul(s2[t<<1|1],tag2[t],M);
		mul(s3[t<<1],tag3[t],M2);
		mul(s3[t<<1|1],tag3[t],M2);
		mul(s4[t<<1],tag4[t],M2);
		mul(s4[t<<1|1],tag4[t],M2);
		mul(s5[t<<1],tag5[t],M3);
		mul(s5[t<<1|1],tag5[t],M3);
		mul(s6[t<<1],tag6[t],M3);
		mul(s6[t<<1|1],tag6[t],M3);
		tag[t]=0,tag1[t]=tag2[t]=tag3[t]=tag4[t]=tag5[t]=tag6[t]=1;
	}
}
void add(int t,int l,int r,int x,int y,int v,int v1,int v2,int v3,int v4,int v5,int v6){
	if (x<=l && r<=y){
		s0[t]+=1ll*(r-l+1)*v;
		mul(s1[t],v1,M);
		mul(s2[t],v2,M);
		mul(s3[t],v3,M2);
		mul(s4[t],v4,M2);
		mul(s5[t],v5,M3);
		mul(s6[t],v6,M3);
		tag[t]+=v;
		mul(tag1[t],v1,M);
		mul(tag2[t],v2,M);
		mul(tag3[t],v3,M2);
		mul(tag4[t],v4,M2);
		mul(tag5[t],v5,M3);
		mul(tag6[t],v6,M3);
		return;
	}
	down(t,l,r);
	int mid=(l+r)>>1;
	if (x<=mid) add(t<<1,l,mid,x,y,v,v1,v2,v3,v4,v5,v6);
	if (mid<y) add(t<<1|1,mid+1,r,x,y,v,v1,v2,v3,v4,v5,v6);
	s0[t]=s0[t<<1]+s0[t<<1|1];
	s1[t]=sum(s1[t<<1],s1[t<<1|1],M);
	s2[t]=sum(s2[t<<1],s2[t<<1|1],M);
	s3[t]=sum(s3[t<<1],s3[t<<1|1],M2);
	s4[t]=sum(s4[t<<1],s4[t<<1|1],M2);
	s5[t]=sum(s5[t<<1],s5[t<<1|1],M3);
	s6[t]=sum(s6[t<<1],s6[t<<1|1],M3);
}
node query(int t,int l,int r,int x,int y){
	if (x<=l && r<=y) return {s0[t],s1[t],s2[t],s3[t],s4[t],s5[t],s6[t]};
	down(t,l,r);
	int mid=(l+r)>>1;
	node tmp={0,0,0,0,0,0,0};
	if (x<=mid){
		node pp=query(t<<1,l,mid,x,y);
		tmp.s+=pp.s;
		tmp.x=sum(tmp.x,pp.x,M);
		tmp.y=sum(tmp.y,pp.y,M);
		tmp.z=sum(tmp.z,pp.z,M2);
		tmp.w=sum(tmp.w,pp.w,M2);
		tmp.a=sum(tmp.a,pp.a,M3);
		tmp.b=sum(tmp.b,pp.b,M3);
	}
	if (mid<y){
		node pp=query(t<<1|1,mid+1,r,x,y);
		tmp.s+=pp.s;
		tmp.x=sum(tmp.x,pp.x,M);
		tmp.y=sum(tmp.y,pp.y,M);
		tmp.z=sum(tmp.z,pp.z,M2);
		tmp.w=sum(tmp.w,pp.w,M2);
		tmp.a=sum(tmp.a,pp.a,M3);
		tmp.b=sum(tmp.b,pp.b,M3);
	}
	return tmp;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for (i=1;i<=n;i++) cin>>a[i],a[i]++;
	XX=pw(X,M-2,M);
	YY=pw(Y,M2-2,M2);
	ZZ=pw(Z,M3-2,M3);
	build(1,1,n);
	for (;q--;){
		cin>>op>>x>>y;
		if (op==1){
			cin>>v;
			add(1,1,n,x,y,v,pw(X,v,M),pw(XX,v,M),pw(Y,v,M2),pw(YY,v,M2),pw(Z,v,M3),pw(ZZ,v,M3));
		}else{
			node tmp=query(1,1,n,x,y);
			ll t=tmp.s;
//			cout<<t<<endl;
			if ((t*2)%(y-x+1)){
				cout<<"NO\n";
				continue;
			}
			t=t*2/(y-x+1);
			if (1ll*tmp.y*pw(X,t,M)%M==tmp.x
			&& 1ll*tmp.w*pw(Y,t,M2)%M2==tmp.z
			&& 1ll*tmp.b*pw(Z,t,M3)%M3==tmp.a) cout<<"YES\n";
			else cout<<"NO\n";
		}
	}
}
/*
8 7
4 2 3 1 2 8 9 2
2 4 7
2 1 4
2 1 6
1 4 7 10
2 4 7
1 1 1 6
2 1 4
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 30208kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100

Wrong Answer

time: 438ms

memory: 53240kb

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected NO, found YES [226th token]