QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527389 | #9155. 集合 | bribritt | 100 ✓ | 183ms | 36828kb | C++17 | 1.4kb | 2024-08-22 14:50:16 | 2024-08-22 14:50:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
const int N = 200069;
const int M = 600069;
const int BUC = 600;
#define what(x) cerr<<#x<<" is "<<(x)<<endl
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
#ifdef TEST
n=2e5;m=6e5;q=1e6;
#else
cin >> n >> m >> q;
#endif
mt19937_64 rng(12102010);
vector<i64> val(n);
for(int i=0;i<n;i++) val[i]=rng();
vector<vector<int>> A(n,vector<int>(3,0)), B(n,vector<int>(3,0));
#ifdef TEST
for(int i=0;i<n;i++) {
A[i][0]=rng()%m;
A[i][1]=rng()%m;
A[i][2]=rng()%m;
B[i][0]=rng()%m;
B[i][1]=rng()%m;
B[i][2]=rng()%m;
}
#else
for(int i=0;i<n;i++) cin>>A[i][0]>>A[i][1]>>A[i][2];
for(int i=0;i<n;i++) cin>>B[i][0]>>B[i][1]>>B[i][2];
for(int i=0;i<n;i++) for(int j=0;j<3;j++) A[i][j]--,B[i][j]--;
#endif
i64 diff = 0;
vector<i64> av(m,0), bv(m,0);
auto toggle = [&val,&A,&B,&av,&bv,&diff](int x) {
for(int i=0;i<3;++i) {
diff -= av[A[x][i]];
diff += (av[A[x][i]]^=val[x]);
diff += bv[B[x][i]];
diff -= (bv[B[x][i]]^=val[x]);
}
};
int fst[n];
for(int i=0,j=0;i<n;i++) {
toggle(i);
while(diff) toggle(j++);
fst[i]=j;
}
for(int l,r,i=0;i<q;i++) {
#ifdef TEST
l=rng()%n, r=rng()%n;
if(l>r) swap(l,r);
#else
cin >> l >> r;
--l; --r;
#endif
cout << (l<fst[r]?"No\n":"Yes\n");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3540kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3588kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3660kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3816kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3816kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3812kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 3608kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 3612kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 3604kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 3712kb
Pretest #11:
score: 5
Accepted
time: 72ms
memory: 27280kb
Pretest #12:
score: 5
Accepted
time: 57ms
memory: 27532kb
Pretest #13:
score: 5
Accepted
time: 1ms
memory: 4120kb
Pretest #14:
score: 5
Accepted
time: 1ms
memory: 4220kb
Pretest #15:
score: 5
Accepted
time: 99ms
memory: 3892kb
Pretest #16:
score: 5
Accepted
time: 106ms
memory: 3924kb
Pretest #17:
score: 5
Accepted
time: 7ms
memory: 5576kb
Pretest #18:
score: 5
Accepted
time: 5ms
memory: 6484kb
Pretest #19:
score: 5
Accepted
time: 178ms
memory: 27572kb
Pretest #20:
score: 5
Accepted
time: 183ms
memory: 36828kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3616kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3652kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3644kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3584kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 3644kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3588kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 3596kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 3564kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 3680kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 3912kb
Test #11:
score: 5
Accepted
time: 68ms
memory: 27404kb
Test #12:
score: 5
Accepted
time: 67ms
memory: 27264kb
Test #13:
score: 5
Accepted
time: 1ms
memory: 3836kb
Test #14:
score: 5
Accepted
time: 1ms
memory: 3952kb
Test #15:
score: 5
Accepted
time: 105ms
memory: 4056kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 3988kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 5464kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 6500kb
Test #19:
score: 5
Accepted
time: 162ms
memory: 27784kb
Test #20:
score: 5
Accepted
time: 180ms
memory: 36764kb
Extra Test:
score: 0
Extra Test Passed