QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492921#9155. 集合dengziyue100 ✓746ms37588kbC++142.4kb2024-07-26 17:14:112024-07-26 17:14:11

Judging History

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

  • [2024-07-26 17:14:11]
  • 评测
  • 测评结果:100
  • 用时:746ms
  • 内存:37588kb
  • [2024-07-26 17:14:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define max_n 600000
#define mod 998244353ll
mt19937 rnd(998244353);
long long ba[max_n+2];
int n;
int m;
int q;
int a[max_n+2][3];
int b[max_n+2][3];
long long cnta1[max_n+2]; 
long long cntb1[max_n+2];
long long cnta2[max_n+2]; 
long long cntb2[max_n+2];
long long suma1=1,sumb1=1,suma2=1,sumb2=1;
int pos[max_n+2];
inline long long askrnd(){
	return (1ll*(rnd()%1000000ll)*1000000ll+(rnd()%1000000ll))%998244352ll+1;
}
inline long long qp(long long a,long long b){
	long long res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod; b>>=1;
	}
	return res;
}
inline void adda(int x,int y){
	suma1=suma1*qp(cnta1[x],mod-2)%mod;
	cnta1[x]=(cnta1[x]+ba[y])%mod;
	suma1=suma1*cnta1[x]%mod;
	suma2=suma2*qp(cnta2[x],mod-2)%mod;
	cnta2[x]=(cnta2[x]+ba[y+n])%mod;
	suma2=suma2*cnta2[x]%mod;
}
inline void addb(int x,int y){
	sumb1=sumb1*qp(cntb1[x],mod-2)%mod;
	cntb1[x]=(cntb1[x]+ba[y])%mod;
	sumb1=sumb1*cntb1[x]%mod;
	sumb2=sumb2*qp(cntb2[x],mod-2)%mod;
	cntb2[x]=(cntb2[x]+ba[y+n])%mod;
	sumb2=sumb2*cntb2[x]%mod;
}
inline void dela(int x,int y){
	suma1=suma1*qp(cnta1[x],mod-2)%mod;
	cnta1[x]=(cnta1[x]-ba[y]+mod)%mod;
	suma1=suma1*cnta1[x]%mod;
	suma2=suma2*qp(cnta2[x],mod-2)%mod;
	cnta2[x]=(cnta2[x]-ba[y+n]+mod)%mod;
	suma2=suma2*cnta2[x]%mod;
}
inline void delb(int x,int y){
	sumb1=sumb1*qp(cntb1[x],mod-2)%mod;
	cntb1[x]=(cntb1[x]-ba[y]+mod)%mod;
	sumb1=sumb1*cntb1[x]%mod;
	sumb2=sumb2*qp(cntb2[x],mod-2)%mod;
	cntb2[x]=(cntb2[x]-ba[y+n]+mod)%mod;
	sumb2=sumb2*cntb2[x]%mod;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("P10785_1.in","r",stdin);
	freopen("P10785_1.out","w",stdout);
	#endif
	for(int i=1;i<=max_n;++i)ba[i]=askrnd();
	unique(ba+1,ba+max_n+1);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=0;j<=2;++j)scanf("%d",a[i]+j);
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=2;++j)scanf("%d",b[i]+j);
	}
	for(int i=1;i<=m;++i)cnta1[i]=cntb1[i]=cnta2[i]=cntb2[i]=1;
	for(int i=1;i<=n;++i)pos[i]=i;
	for(int l=1,r=0;l<=n;){
		if(suma1==sumb1&&suma2==sumb2){
			pos[l]=max(pos[l],r++);
			if(r>n)break;
			for(int j=0;j<=2;++j){adda(a[r][j],r); addb(b[r][j],r);}
		}
		else{
			for(int j=0;j<=2;++j){dela(a[l][j],l); delb(b[l][j],l);}
			++l;
		}
	}
	for(int i=2;i<=n;++i)pos[i]=max(pos[i],pos[i-1]);
	for(int ca=1,l,r;ca<=q;++ca){
		scanf("%d%d",&l,&r);
		if(pos[l]>=r)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 5ms
memory: 22228kb

Pretest #4:

score: 5
Accepted
time: 7ms
memory: 22660kb

Pretest #5:

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

Pretest #6:

score: 5
Accepted
time: 7ms
memory: 21576kb

Pretest #7:

score: 5
Accepted
time: 8ms
memory: 21868kb

Pretest #8:

score: 5
Accepted
time: 4ms
memory: 21344kb

Pretest #9:

score: 5
Accepted
time: 23ms
memory: 21700kb

Pretest #10:

score: 5
Accepted
time: 26ms
memory: 21424kb

Pretest #11:

score: 5
Accepted
time: 614ms
memory: 29304kb

Pretest #12:

score: 5
Accepted
time: 614ms
memory: 26008kb

Pretest #13:

score: 5
Accepted
time: 14ms
memory: 22740kb

Pretest #14:

score: 5
Accepted
time: 10ms
memory: 25696kb

Pretest #15:

score: 5
Accepted
time: 129ms
memory: 20884kb

Pretest #16:

score: 5
Accepted
time: 118ms
memory: 22360kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 58ms
memory: 23436kb

Pretest #19:

score: 5
Accepted
time: 733ms
memory: 28372kb

Pretest #20:

score: 5
Accepted
time: 746ms
memory: 36372kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

score: 5
Accepted
time: 4ms
memory: 21084kb

Test #4:

score: 5
Accepted
time: 7ms
memory: 21084kb

Test #5:

score: 5
Accepted
time: 8ms
memory: 22280kb

Test #6:

score: 5
Accepted
time: 4ms
memory: 21844kb

Test #7:

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

Test #8:

score: 5
Accepted
time: 5ms
memory: 22068kb

Test #9:

score: 5
Accepted
time: 25ms
memory: 21048kb

Test #10:

score: 5
Accepted
time: 22ms
memory: 21428kb

Test #11:

score: 5
Accepted
time: 614ms
memory: 27124kb

Test #12:

score: 5
Accepted
time: 611ms
memory: 26856kb

Test #13:

score: 5
Accepted
time: 10ms
memory: 21048kb

Test #14:

score: 5
Accepted
time: 7ms
memory: 21008kb

Test #15:

score: 5
Accepted
time: 121ms
memory: 21668kb

Test #16:

score: 5
Accepted
time: 126ms
memory: 22632kb

Test #17:

score: 5
Accepted
time: 67ms
memory: 22184kb

Test #18:

score: 5
Accepted
time: 67ms
memory: 24612kb

Test #19:

score: 5
Accepted
time: 722ms
memory: 27348kb

Test #20:

score: 5
Accepted
time: 737ms
memory: 37588kb

Extra Test:

score: 0
Extra Test Passed