QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492742 | #9155. 集合 | leihonglongyin | 100 ✓ | 517ms | 61468kb | C++20 | 1.1kb | 2024-07-26 15:40:18 | 2024-07-26 15:40:20 |
Judging History
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