QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511244#9155. 集合Line12100 ✓617ms25100kbC++141.8kb2024-08-09 17:58:482024-08-09 17:58:53

Judging History

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

  • [2024-08-09 17:58:53]
  • 评测
  • 测评结果:100
  • 用时:617ms
  • 内存:25100kb
  • [2024-08-09 17:58:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll B1=600007;
const ll P1=998244353;
const ll P2=1000000007;
const int N=600009;
const int M=600009;
int n,m,q,bst[N];
ll s[M],t[M],sum1=1,sum2=1;
struct Set{int x,y,z;} a[N],b[N];
ll ksm(ll a,ll b,ll c){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%c;
		a=a*a%c;
		b>>=1;
	}
	return ans;
}
ll inv(ll a,ll b){
	return ksm(a,b-2,b);
}
void insert1(int x,int i){
	sum1=sum1*inv(s[x],P2)%P2;
	assert(s[x]%P2!=0);
	(s[x]+=ksm(B1,i,P1))%=P1;
	sum1=sum1*s[x]%P2;
}
void insert2(int x,int i){
	sum2=sum2*inv(t[x],P2)%P2;
	assert(t[x]%P2!=0);
	(t[x]+=ksm(B1,i,P1))%=P1;
	sum2=sum2*t[x]%P2;
}
void delete1(int x,int i){
	sum1=sum1*inv(s[x],P2)%P2;
	assert(s[x]%P2!=0);
	(s[x]=s[x]-ksm(B1,i,P1)+P1)%=P1;
	sum1=sum1*s[x]%P2;
}
void delete2(int x,int i){
	sum2=sum2*inv(t[x],P2)%P2;
	assert(t[x]%P2!=0);
	(t[x]=t[x]-ksm(B1,i,P1)+P1)%=P1;
	sum2=sum2*t[x]%P2;
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	sum1=sum2=1;
	for(int i=1;i<=n;i++)
	    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	for(int i=1;i<=n;i++)
	    scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
	for(int i=1;i<=n*3;i++)
	    s[i]=t[i]=1;
	int r=0;
	for(int l=1;l<=n;l++){
		bst[l]=max(bst[l-1],l);
		if(sum1==sum2)bst[l]=max(bst[l],r);
		while((sum1==sum2||r<l)&&r<=n-1){
			r++;
			insert1(a[r].x,r);
			insert1(a[r].y,r);
			insert1(a[r].z,r);
			insert2(b[r].x,r);
			insert2(b[r].y,r);
			insert2(b[r].z,r);
			if(sum1!=sum2)break;
			bst[l]=r;
		}
		delete1(a[l].x,l);
		delete1(a[l].y,l);
		delete1(a[l].z,l);
		delete2(b[l].x,l);
		delete2(b[l].y,l);
		delete2(b[l].z,l);
	}
	int ql,qr;
	for(int i=1;i<=q;i++){
		scanf("%d%d",&ql,&qr);
		if(bst[ql]>=qr)puts("Yes");
		else puts("No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 21ms
memory: 9968kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 479ms
memory: 22692kb

Pretest #12:

score: 5
Accepted
time: 478ms
memory: 24332kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 116ms
memory: 9808kb

Pretest #16:

score: 5
Accepted
time: 113ms
memory: 9780kb

Pretest #17:

score: 5
Accepted
time: 41ms
memory: 10200kb

Pretest #18:

score: 5
Accepted
time: 46ms
memory: 12192kb

Pretest #19:

score: 5
Accepted
time: 591ms
memory: 22888kb

Pretest #20:

score: 5
Accepted
time: 615ms
memory: 21680kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 18ms
memory: 9896kb

Test #11:

score: 5
Accepted
time: 483ms
memory: 22840kb

Test #12:

score: 5
Accepted
time: 471ms
memory: 23960kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 113ms
memory: 9804kb

Test #16:

score: 5
Accepted
time: 116ms
memory: 9908kb

Test #17:

score: 5
Accepted
time: 45ms
memory: 10088kb

Test #18:

score: 5
Accepted
time: 46ms
memory: 10200kb

Test #19:

score: 5
Accepted
time: 584ms
memory: 25100kb

Test #20:

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

Extra Test:

score: 0
Extra Test Passed