QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490231 | #9155. 集合 | DaiRuiChen007 | 100 ✓ | 540ms | 20024kb | C++17 | 1013b | 2024-07-25 13:15:26 | 2024-07-25 13:15:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
mt19937_64 rnd(time(0));
const int MAXN=2e5+5,MAXM=6e5+5;
int n,m,q,a[MAXN][3],b[MAXN][3],rp[MAXN];
ull hv[MAXN],A[MAXM],B[MAXM];
signed main() {
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;++i) hv[i]=rnd();
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,j=0;i<=n;++i) {
while(j<n) {
vector <ull> mA,mB;
for(int k:a[j+1]) mA.push_back(A[k]^hv[j+1]),mB.push_back(A[k]);
for(int k:b[j+1]) mB.push_back(B[k]^hv[j+1]),mA.push_back(B[k]);
sort(mA.begin(),mA.end()),sort(mB.begin(),mB.end());
bool flg=1;
for(int k:{0,1,2,3,4,5}) flg&=(mA[k]==mB[k]);
if(!flg) break;
++j;
for(int k:a[j]) A[k]^=hv[j];
for(int k:b[j]) B[k]^=hv[j];
}
rp[i]=j;
for(int k:a[i]) A[k]^=hv[i];
for(int k:b[i]) B[k]^=hv[i];
}
for(int l,r;q--;) cin>>l>>r,cout<<(r<=rp[l]?"Yes\n":"No\n");
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 11820kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9768kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 11812kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 10068kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9816kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9880kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9820kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9984kb
Pretest #9:
score: 5
Accepted
time: 71ms
memory: 9768kb
Pretest #10:
score: 5
Accepted
time: 56ms
memory: 9812kb
Pretest #11:
score: 5
Accepted
time: 199ms
memory: 10964kb
Pretest #12:
score: 5
Accepted
time: 208ms
memory: 11584kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 12116kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 9904kb
Pretest #15:
score: 5
Accepted
time: 292ms
memory: 9840kb
Pretest #16:
score: 5
Accepted
time: 283ms
memory: 9904kb
Pretest #17:
score: 5
Accepted
time: 15ms
memory: 9824kb
Pretest #18:
score: 5
Accepted
time: 17ms
memory: 12828kb
Pretest #19:
score: 5
Accepted
time: 412ms
memory: 10816kb
Pretest #20:
score: 5
Accepted
time: 531ms
memory: 20024kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 11812kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 10068kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 10068kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10052kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 11880kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10068kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 10072kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9772kb
Test #9:
score: 5
Accepted
time: 39ms
memory: 9812kb
Test #10:
score: 5
Accepted
time: 63ms
memory: 11816kb
Test #11:
score: 5
Accepted
time: 187ms
memory: 12416kb
Test #12:
score: 5
Accepted
time: 183ms
memory: 11196kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 9972kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 10076kb
Test #15:
score: 5
Accepted
time: 251ms
memory: 12120kb
Test #16:
score: 5
Accepted
time: 356ms
memory: 11908kb
Test #17:
score: 5
Accepted
time: 16ms
memory: 9848kb
Test #18:
score: 5
Accepted
time: 16ms
memory: 10716kb
Test #19:
score: 5
Accepted
time: 540ms
memory: 11572kb
Test #20:
score: 5
Accepted
time: 464ms
memory: 20024kb
Extra Test:
score: 0
Extra Test Passed