QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527436 | #9155. 集合 | TheRaptor | 100 ✓ | 179ms | 20144kb | C++17 | 1.5kb | 2024-08-22 15:18:21 | 2024-08-22 15:18:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
long long tag[n+1];
mt19937_64 rng(999);
for(int i=0; i<=n; i++) tag[i]=rng();
tuple<int,int,int> arr[n+1],brr[n+1];
long long in[2][m+1];
memset(in,0,sizeof(in));
for(int i=1; i<=n; i++){
int a,b,c;
cin >> a >> b >> c;
arr[i]={a,b,c};
}
for(int i=1; i<=n; i++){
int a,b,c;
cin >> a >> b >> c;
brr[i]={a,b,c};
}
unsigned long long tot=0;
int cnt=1;
int l[n+1];
for(int i=1; i<=n; i++){
int a,b,c;
tie(a,b,c)=arr[i];
tot-=in[0][a];
in[0][a]^=tag[i];
tot+=in[0][a];
tot-=in[0][b];
in[0][b]^=tag[i];
tot+=in[0][b];
tot-=in[0][c];
in[0][c]^=tag[i];
tot+=in[0][c];
tie(a,b,c)=brr[i];
tot+=in[1][a];
in[1][a]^=tag[i];
tot-=in[1][a];
tot+=in[1][b];
in[1][b]^=tag[i];
tot-=in[1][b];
tot+=in[1][c];
in[1][c]^=tag[i];
tot-=in[1][c];
while(tot){
tie(a,b,c)=arr[cnt];
tot-=in[0][a];
in[0][a]^=tag[cnt];
tot+=in[0][a];
tot-=in[0][b];
in[0][b]^=tag[cnt];
tot+=in[0][b];
tot-=in[0][c];
in[0][c]^=tag[cnt];
tot+=in[0][c];
tie(a,b,c)=brr[cnt];
tot+=in[1][a];
in[1][a]^=tag[cnt];
tot-=in[1][a];
tot+=in[1][b];
in[1][b]^=tag[cnt];
tot-=in[1][b];
tot+=in[1][c];
in[1][c]^=tag[cnt];
tot-=in[1][c];
cnt++;
}
l[i]=cnt;
}
while(q--){
int a,b;
cin >> a >> b;
if(l[b]<=a) cout << "Yes\n";
else cout << "No\n";
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3692kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3604kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3644kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3616kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3680kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3744kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 3684kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 3620kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 3624kb
Pretest #10:
score: 5
Accepted
time: 19ms
memory: 3672kb
Pretest #11:
score: 5
Accepted
time: 55ms
memory: 10716kb
Pretest #12:
score: 5
Accepted
time: 61ms
memory: 10652kb
Pretest #13:
score: 5
Accepted
time: 1ms
memory: 3704kb
Pretest #14:
score: 5
Accepted
time: 1ms
memory: 3784kb
Pretest #15:
score: 5
Accepted
time: 97ms
memory: 3748kb
Pretest #16:
score: 5
Accepted
time: 104ms
memory: 3844kb
Pretest #17:
score: 5
Accepted
time: 5ms
memory: 4444kb
Pretest #18:
score: 5
Accepted
time: 3ms
memory: 5380kb
Pretest #19:
score: 5
Accepted
time: 167ms
memory: 10676kb
Pretest #20:
score: 5
Accepted
time: 179ms
memory: 20144kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3696kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3664kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3688kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3640kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 3692kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3612kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 3676kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 3684kb
Test #9:
score: 5
Accepted
time: 15ms
memory: 3684kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 3744kb
Test #11:
score: 5
Accepted
time: 59ms
memory: 10776kb
Test #12:
score: 5
Accepted
time: 57ms
memory: 10776kb
Test #13:
score: 5
Accepted
time: 1ms
memory: 3780kb
Test #14:
score: 5
Accepted
time: 1ms
memory: 3784kb
Test #15:
score: 5
Accepted
time: 99ms
memory: 3696kb
Test #16:
score: 5
Accepted
time: 104ms
memory: 3844kb
Test #17:
score: 5
Accepted
time: 6ms
memory: 4400kb
Test #18:
score: 5
Accepted
time: 6ms
memory: 5252kb
Test #19:
score: 5
Accepted
time: 162ms
memory: 10676kb
Test #20:
score: 5
Accepted
time: 164ms
memory: 20028kb
Extra Test:
score: 0
Extra Test Passed