QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#835853#9774. Same Sumnb_jzyWA 950ms27532kbC++142.5kb2024-12-28 15:04:272024-12-28 15:04:27

Judging History

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

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2024-12-28 15:04:27]
  • 评测
  • 测评结果:WA
  • 用时:950ms
  • 内存:27532kb
  • [2024-12-28 15:04:27]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
const int mod=1e9+7,P=19260817,maxn=5e5+5,inf=1e12;
int n,q,a[maxn],t[maxn<<2][2],la[maxn<<2],sum[maxn<<2];
struct node{
	int sum,p1,p2;
};
int poww(int x,int y){
	int res=1;
	while(y>0){
		if(y&1){
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
void shutdown(int p,int l,int r){
	if(la[p]>0){
		la[ls(p)]+=la[p],la[rs(p)]+=la[p];
		int mid=(l+r)>>1;
		sum[ls(p)]+=la[p]*(mid-l+1),sum[rs(p)]+=la[p]*(r-mid);
		int mi=poww(P,la[p]);
		t[ls(p)][0]=t[ls(p)][0]*mi%mod;t[rs(p)][0]=t[rs(p)][0]*mi%mod;
		mi=poww(mi,mod-2);
		t[ls(p)][1]=t[ls(p)][1]*mi%mod,t[rs(p)][1]==t[rs(p)][1]*mi%mod;
		la[p]=0;
	}
}
void build(int p,int l,int r){
	if(l==r){
		t[p][0]=poww(P,a[l]);t[p][1]=poww(P,inf-a[l]);sum[p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
	t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
	sum[p]=sum[ls(p)]+sum[rs(p)];
}
void add(int p,int l,int r,int x,int y,int z){
	if(l>=x&&r<=y){
		la[p]+=z;
		int mi=poww(P,z); 
		t[p][0]=t[p][0]*mi%mod;t[p][1]=t[p][1]*poww(mi,mod-2)%mod;
		sum[p]+=(r-l+1)*z;
		return;
	}
	shutdown(p,l,r);
	int mid=(l+r)>>1;
	if(x<=mid&&y>=l){
		add(ls(p),l,mid,x,y,z);
	}
	if(y>mid&&x<=r){
		add(rs(p),mid+1,r,x,y,z); 
	}
	t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
	t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
	sum[p]=sum[ls(p)]+sum[rs(p)];
}
node query(int p,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		return {sum[p],t[p][0],t[p][1]};
	}
	shutdown(p,l,r);
	int mid=(l+r)>>1;
	node res={0,0,0},ll;
	if(x<=mid&&y>=l){
		ll=query(ls(p),l,mid,x,y);
		res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
	}
	if(y>mid&&x<=r){
		ll=query(rs(p),mid+1,r,x,y);
		res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
	}
	res.p1%=mod,res.p2%=mod;
	return res;
}
signed main(){
//	freopen("1.in","r",stdin);
	int cnt=0;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int op,l,r,v;
		cin>>op;
		if(op==1){
			cin>>l>>r>>v;
			add(1,1,n,l,r,v);
		}
		else{
			cin>>l>>r;
			cnt++;
			node res=query(1,1,n,l,r);
			if(res.sum%((r-l+1)/2)==0){
				int del=res.sum/((r-l+1)/2);
				del=poww(poww(P,inf-del),mod-2);
				if(res.p2*del%mod==res.p1){
					cout<<"YES\n";
				}
				else{
					cout<<"NO\n";
				}
			}
			else{
				if(cnt==464){
					return 1;
				}
				cout<<"NO\n";
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7656kb

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: 950ms
memory: 27532kb

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 YES, found NO [464th token]