QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492742#9155. 集合leihonglongyin100 ✓517ms61468kbC++201.1kb2024-07-26 15:40:182024-07-26 15:40:20

Judging History

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

  • [2024-07-26 15:40:20]
  • 评测
  • 测评结果:100
  • 用时:517ms
  • 内存:61468kb
  • [2024-07-26 15:40:18]
  • 提交

answer

#include<bits/stdc++.h> 
using namespace std;const int N=2e5+5,M=N*3,mod=1e9+7,Bs=131;mt19937 R(time(0));
int n,m,q,a[N][3],b[N][3],w[N],ans[N],asw,sa[M],sb[M],bs[N],la[M],lb[M];unordered_map<int,int>s;
void add(int now,int v){if(s[now]==0)asw++;s[now]+=v;if(s[now]==0)asw--;}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q,bs[0]=1;for(int i=1;i<=n;i++)w[i]=R()%mod,bs[i]=1ll*bs[i-1]*Bs%mod;
	for(int i=1;i<=n;i++)for(int j=0;j<3;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)for(int j=0;j<3;j++)cin>>b[i][j];
	for(int j=1,i=1;i<=n;i++){
		for(int to,k=0;k<3;k++)to=a[i][k],add(sa[to],-1),la[to]++,sa[to]=(1ll*sa[to]*Bs+w[i])%mod,add(sa[to],1);
		for(int to,k=0;k<3;k++)to=b[i][k],add(sb[to],1),lb[to]++,sb[to]=(1ll*sb[to]*Bs+w[i])%mod,add(sb[to],-1);
		while(j<=i&&asw){
			for(int to,k=0;k<3;k++)to=a[j][k],add(sa[to],-1),la[to]--,sa[to]=(sa[to]-1ll*w[j]*bs[la[to]]%mod+mod)%mod,add(sa[to],1);
			for(int to,k=0;k<3;k++)to=b[j][k],add(sb[to],1),lb[to]--,sb[to]=(sb[to]-1ll*w[j]*bs[lb[to]]%mod+mod)%mod,add(sb[to],-1);
			j++;
		}ans[i]=j;
	}for(int x,y,i=1;i<=q;i++)cin>>x>>y,cout<<(ans[y]>x?"No":"Yes")<<"\n";
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 19ms
memory: 13972kb

Pretest #10:

score: 5
Accepted
time: 20ms
memory: 14196kb

Pretest #11:

score: 5
Accepted
time: 460ms
memory: 61468kb

Pretest #12:

score: 5
Accepted
time: 417ms
memory: 59348kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 115ms
memory: 14580kb

Pretest #16:

score: 5
Accepted
time: 119ms
memory: 14596kb

Pretest #17:

score: 5
Accepted
time: 19ms
memory: 18364kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 510ms
memory: 59076kb

Pretest #20:

score: 5
Accepted
time: 517ms
memory: 58744kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 5
Accepted
time: 20ms
memory: 12140kb

Test #11:

score: 5
Accepted
time: 392ms
memory: 59632kb

Test #12:

score: 5
Accepted
time: 347ms
memory: 54908kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 119ms
memory: 16372kb

Test #16:

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

Test #17:

score: 5
Accepted
time: 19ms
memory: 18152kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 509ms
memory: 57592kb

Test #20:

score: 5
Accepted
time: 482ms
memory: 58808kb

Extra Test:

score: 0
Extra Test Passed