QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#604288 | #9155. 集合 | Sai_tqwq | 100 ✓ | 302ms | 25640kb | C++14 | 1.2kb | 2024-10-02 08:49:26 | 2024-10-02 08:49:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define double long double
#define endl '\n'
mt19937 rnd(time(NULL));
int qpow(int a,int b,int res=1){
while(b){if(b&1)res=res*a;a=a*a;b>>=1;}
return res;
}
int n,m,q,a[200009][3],b[200009][3],mxr[200009];
int sa[600009],sb[600009];
int h1[200009],sd,sd2,sd3,ta,tb;
int h2(int x){return (sd*x<<10)^x^sd2^sd3;}
void insert(int x,int f){
for(int i=0;i<3;i++){
ta-=h2(sa[a[x][i]]);
sa[a[x][i]]+=f*h1[x];
ta+=h2(sa[a[x][i]]);
tb-=h2(sb[b[x][i]]);
sb[b[x][i]]+=f*h1[x];
tb+=h2(sb[b[x][i]]);
}
}
signed main(){
// freopen("set.in","r",stdin);
// freopen("set.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)cin>>a[i][0]>>a[i][1]>>a[i][2];
for(int i=1;i<=n;i++)cin>>b[i][0]>>b[i][1]>>b[i][2];
for(int i=1;i<=n;i++)mxr[i]=n;
for(int p=0;p<20;p++){
sd=rnd();sd2=rnd();sd3=rnd();for(int i=1;i<=n;i++)h1[i]=rnd();ta=tb=0;
for(int i=1,j=0;i<=n;insert(i++,-1)){
while(j<=n&&ta==tb)insert(++j,1);
mxr[i]=min(mxr[i],j-1);
}
}
while(q--){int l,r;cin>>l>>r;cout<<(mxr[l]>=r?"Yes\n":"No\n");}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9908kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 9912kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9908kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9868kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9920kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7740kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9872kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9820kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 9784kb
Pretest #10:
score: 5
Accepted
time: 15ms
memory: 7792kb
Pretest #11:
score: 5
Accepted
time: 157ms
memory: 17180kb
Pretest #12:
score: 5
Accepted
time: 159ms
memory: 17324kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 9900kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 9876kb
Pretest #15:
score: 5
Accepted
time: 93ms
memory: 9896kb
Pretest #16:
score: 5
Accepted
time: 93ms
memory: 9880kb
Pretest #17:
score: 5
Accepted
time: 15ms
memory: 9948kb
Pretest #18:
score: 5
Accepted
time: 19ms
memory: 12960kb
Pretest #19:
score: 5
Accepted
time: 266ms
memory: 19416kb
Pretest #20:
score: 5
Accepted
time: 302ms
memory: 25604kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 9916kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 9868kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9868kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9876kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9852kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9808kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9916kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 7828kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 9880kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 9772kb
Test #11:
score: 5
Accepted
time: 163ms
memory: 16956kb
Test #12:
score: 5
Accepted
time: 154ms
memory: 17416kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 9844kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 9896kb
Test #15:
score: 5
Accepted
time: 93ms
memory: 9876kb
Test #16:
score: 5
Accepted
time: 101ms
memory: 7856kb
Test #17:
score: 5
Accepted
time: 15ms
memory: 10080kb
Test #18:
score: 5
Accepted
time: 15ms
memory: 12996kb
Test #19:
score: 5
Accepted
time: 257ms
memory: 19452kb
Test #20:
score: 5
Accepted
time: 296ms
memory: 25640kb
Extra Test:
score: 0
Extra Test Passed