QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#856944#9774. Same Sumyuanyq5523WA 1031ms100984kbC++143.5kb2025-01-14 21:09:372025-01-14 21:09:42

Judging History

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

  • [2025-01-14 21:09:42]
  • 评测
  • 测评结果:WA
  • 用时:1031ms
  • 内存:100984kb
  • [2025-01-14 21:09:37]
  • 提交

answer

#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e5+5;
int n,q,b[N];

struct segmentTree{
	int op,kd;
	LL P,mod,a[N],tr[N<<2],tag[N<<2];
	
	LL quick_pow(LL a,LL b){
		LL res=1;
		while (b){
			if (b&1) res=res*a%mod;
			a=a*a%mod;
			b>>=1;
		}
		return res;
	}
	
	void push_up(int u){
		tr[u]=(tr[u<<1]+tr[u<<1|1]);
		if (op==1) tr[u]%=mod;
	}
	
	void push_down(int u,int l,int r){
		if (op==0){
			if (tag[u]!=0){
				int mid=(l+r)>>1;
				tr[u<<1]+=tag[u]*(r-mid);
				tr[u<<1|1]+=tag[u]*(mid-l+1);
				tag[u<<1]+=tag[u]; tag[u<<1|1]+=tag[u];
				tag[u]=0; return;
			}
		}	
		else{
			if (tag[u]!=1){
				tr[u<<1]=tr[u<<1]*tag[u]%mod;
				tr[u<<1|1]=tr[u<<1|1]*tag[u]%mod;
				tag[u<<1]=tag[u<<1]*tag[u]%mod;
				tag[u<<1|1]=tag[u<<1|1]*tag[u]%mod;
				tag[u]=1;
			}
		}
	}
	
	void build(int u,int l,int r){
		tag[u]=op; tr[u]=0;
		if (l==r){
			tr[u]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		push_up(u);
	}
	
	void update(int u,int l,int r,int L,int R,LL v){
		if (l>R || r<L) return;
		if (L<=l && r<=R){
			if (op==0){
				tr[u]+=v*(r-l+1);
				tag[u]+=v;
				return;
			}
			else{
				tr[u]=tr[u]*v%mod;
				tag[u]=tag[u]*v%mod;
				return;
			}
		}
		push_down(u,l,r);
		int mid=(l+r)>>1;
		update(u<<1,l,mid,L,R,v);
		update(u<<1|1,mid+1,r,L,R,v);
		push_up(u);
	}
	
	LL query(int u,int l,int r,int L,int R){
		if (l>R || r<L) return 0;
		if (L<=l && r<=R) return tr[u];
		push_down(u,l,r);
		int mid=(l+r)>>1;
		LL res=query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
		if (op==1) res%=mod;
		return res;
	}
	
	void prework(int cop,int ckd,LL cP,LL cmod){
		op=cop; kd=ckd; P=cP; mod=cmod;
		for (int i=1;i<=n;i++){
			a[i]=b[i];
			if (ckd==1) a[i]=quick_pow(P,a[i]);
			if (ckd==2) a[i]=quick_pow(quick_pow(P,a[i]),mod-2); 
		}
		build(1,1,n);
	}
	
	void update(int l,int r,LL v){
		if (kd==0) update(1,1,n,l,r,v);
		else{
			v=quick_pow(P,v);
			if (kd==1) update(1,1,n,l,r,v);
			else{
				v=quick_pow(v,mod-2);
				update(1,1,n,l,r,v);
			}
		}
	}
}s,segp1,segp2,segp3,segn1,segn2,segn3;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++) cin>>b[i];
	s.prework(0,0,0,0);
	segp1.prework(1,1,100523,1e9+21);
	segp2.prework(1,1,1000639,1e9+181);
	segp3.prework(1,1,1e8+81,1e9+459);
	segn1.prework(1,2,100523,1e9+21);
	segn2.prework(1,2,1000639,1e9+181);
	segn3.prework(1,2,1e8+81,1e9+459);
	while (q--){
		int op; cin>>op;
		if (op==1){
			int l,r; LL v; cin>>l>>r>>v;
			s.update(l,r,v);
			segp1.update(l,r,v);
			segp2.update(l,r,v);
			segp3.update(l,r,v);
			segn1.update(l,r,v);
			segn2.update(l,r,v);
			segn3.update(l,r,v);
		}
		else{
			int l,r; cin>>l>>r;
			LL sum=s.query(1,1,n,l,r);
			if (sum*2%(r-l+1)!=0){
				cout<<"No"<<endl;
				continue;
			}
			LL ave=sum*2/(r-l+1);
			LL q1=segp1.query(1,1,n,l,r),q2=segn1.query(1,1,n,l,r);
			LL q3=segp2.query(1,1,n,l,r),q4=segn2.query(1,1,n,l,r);
			LL q5=segp3.query(1,1,n,l,r),q6=segn3.query(1,1,n,l,r);
		    bool check1=(q1==q2*segn1.quick_pow(segn1.P,ave)%segn1.mod);
		    bool check2=(q3==q4*segn2.quick_pow(segn2.P,ave)%segn2.mod);
		    bool check3=(q5==q6*segn3.quick_pow(segn3.P,ave)%segn3.mod);
		   // cout<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<" "<<check1<<" "<<check2<<endl;
		    if (check1 && check2 && check3) cout<<"Yes"<<endl;
		    else cout<<"No"<<endl;
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1031ms
memory: 100984kb

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]