QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497995#9155. 集合Jie_XuSheng#100 ✓624ms38832kbC++142.1kb2024-07-29 21:32:522024-07-29 21:32:53

Judging History

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

  • [2024-07-29 21:32:53]
  • 评测
  • 测评结果:100
  • 用时:624ms
  • 内存:38832kb
  • [2024-07-29 21:32:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+10,mod=1e9+7,p=1e5+7;
int n,m,q,a[N],b[N],la[N],lb[N],ya[N],yb[N],id[N],x,y,mi[N];
int ksm(int x,int y){
	int rt=1;
	while(y){
		if(y&1) rt=rt*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return rt;
}
int inv(int t){
	if(t==0) return 1;
	return ksm(t,mod-2);
}
void adda(int pl,int t){
	la[t]++;
	x=x*inv(ya[t])%mod;
	ya[t]=ya[t]*p+pl;
	ya[t]%=mod;
	x=x*ya[t]%mod;
}
void addb(int pl,int t){
	lb[t]++;
	y=y*inv(yb[t])%mod;
	yb[t]=yb[t]*p+pl;
	yb[t]%=mod;
	y=y*yb[t]%mod;
}
void dela(int pl,int t){
	la[t]--;
//	cout<<"t "<<t<<" "<<ya[t]<<" ";
	x=x*inv(ya[t])%mod;
	ya[t]=ya[t]-mi[la[t]]*pl%mod;
	ya[t]=(ya[t]%mod+mod)%mod;
//	cout<<ya[t]<<endl;
	if(ya[t]!=0) x=x*ya[t]%mod;
}
void delb(int pl,int t){
	lb[t]--;
//	cout<<"bt "<<t<<" "<<yb[t]<<" ";
	y=y*inv(yb[t])%mod;
	yb[t]=yb[t]-mi[lb[t]]*pl%mod;
	yb[t]=(yb[t]%mod+mod)%mod;
//	cout<<yb[t]<<endl;
	if(yb[t]!=0) y=y*yb[t]%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	mi[0]=1;
	for(int i=1;i<=n;i++) mi[i]=mi[i-1]*p%mod;
//	for(int i=0;i<=m;i++) ya[i]=yb[i]=1;
	x=y=1;
	for(int i=1;i<=3*n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=3*n;i++){
		cin>>b[i];
	}
	int l=1,r=0;
	while(l<=n){
		int fl=0;
		while(r<=n){
			r++;
			if(r==n+1){
				for(int j=l;j<=n;j++){
					id[j]=n+1;
				}
				fl=1;
				break;
			}
			adda(r,a[r*3-2]);
			adda(r,a[r*3-1]);
			adda(r,a[r*3]);
			addb(r,b[r*3-2]);
			addb(r,b[r*3-1]);
			addb(r,b[r*3]);
		//	cout<<"xy "<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
			if(x==y) continue;
			else{
				id[l]=r;
				break;
			}
		}
		if(fl==1) break;
		while(l<=r){
			dela(l,a[l*3-2]);
			dela(l,a[l*3-1]);
			dela(l,a[l*3]);
			delb(l,b[l*3-2]);
			delb(l,b[l*3-1]);
			delb(l,b[l*3]);
			l++;
		//	cout<<"lr "<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
			if(x==y) break;
			else{
				id[l]=r;
			}
		}
	}
/*	for(int i=1;i<=n;i++){
		cout<<"id "<<i<<" "<<id[i]<<endl;
	}*/
	while(q--){
		int l,r;
		cin>>l>>r;
		if(id[l]<=r) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 13832kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 13932kb

Pretest #3:

score: 5
Accepted
time: 2ms
memory: 13840kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 13904kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 13900kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 13908kb

Pretest #7:

score: 5
Accepted
time: 2ms
memory: 13980kb

Pretest #8:

score: 5
Accepted
time: 2ms
memory: 13904kb

Pretest #9:

score: 5
Accepted
time: 80ms
memory: 13892kb

Pretest #10:

score: 5
Accepted
time: 59ms
memory: 13964kb

Pretest #11:

score: 5
Accepted
time: 340ms
memory: 22752kb

Pretest #12:

score: 5
Accepted
time: 342ms
memory: 24784kb

Pretest #13:

score: 5
Accepted
time: 3ms
memory: 13928kb

Pretest #14:

score: 5
Accepted
time: 0ms
memory: 13968kb

Pretest #15:

score: 5
Accepted
time: 292ms
memory: 13860kb

Pretest #16:

score: 5
Accepted
time: 248ms
memory: 14036kb

Pretest #17:

score: 5
Accepted
time: 28ms
memory: 14016kb

Pretest #18:

score: 5
Accepted
time: 31ms
memory: 17108kb

Pretest #19:

score: 5
Accepted
time: 613ms
memory: 24752kb

Pretest #20:

score: 5
Accepted
time: 567ms
memory: 38832kb

Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 13900kb

Test #2:

score: 5
Accepted
time: 2ms
memory: 13980kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 13840kb

Test #4:

score: 5
Accepted
time: 2ms
memory: 13960kb

Test #5:

score: 5
Accepted
time: 2ms
memory: 13916kb

Test #6:

score: 5
Accepted
time: 0ms
memory: 13888kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 13820kb

Test #8:

score: 5
Accepted
time: 2ms
memory: 13868kb

Test #9:

score: 5
Accepted
time: 51ms
memory: 13960kb

Test #10:

score: 5
Accepted
time: 71ms
memory: 13924kb

Test #11:

score: 5
Accepted
time: 336ms
memory: 22668kb

Test #12:

score: 5
Accepted
time: 343ms
memory: 24708kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 13864kb

Test #14:

score: 5
Accepted
time: 6ms
memory: 14004kb

Test #15:

score: 5
Accepted
time: 256ms
memory: 13920kb

Test #16:

score: 5
Accepted
time: 259ms
memory: 14072kb

Test #17:

score: 5
Accepted
time: 32ms
memory: 14076kb

Test #18:

score: 5
Accepted
time: 29ms
memory: 17076kb

Test #19:

score: 5
Accepted
time: 587ms
memory: 24876kb

Test #20:

score: 5
Accepted
time: 624ms
memory: 37428kb

Extra Test:

score: 0
Extra Test Passed