QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527123 | #9155. 集合 | sumi007# | 100 ✓ | 1015ms | 90104kb | C++14 | 1.8kb | 2024-08-22 10:30:53 | 2024-08-22 10:30:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6+5,P = 131;
mt19937 rd(time(0));
ll n,m,q,lim[N],a[N][3],b[N][3],sa[N],sb[N],key_pos[N],ck_a,ck_b;
map<ll,ll> key_s;
int main(){
// freopen("ex_4.in","r",stdin);
// freopen("T1.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
srand(time(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++) key_pos[i] = rd();
for(int r=1,l=1;r<=n;r++){
for(int i=0;i<3;i++) {
ck_a -= key_s[sa[a[r][i]]];
sa[a[r][i]] = sa[a[r][i]]+key_pos[r];
if(key_s.find(sa[a[r][i]]) == key_s.end()) key_s[sa[a[r][i]]] = rd();
ck_a += key_s[sa[a[r][i]]];
}
for(int i=0;i<3;i++) {
ck_b -= key_s[sb[b[r][i]]];
sb[b[r][i]] = sb[b[r][i]]+key_pos[r];
if(key_s.find(sb[b[r][i]]) == key_s.end()) key_s[sb[b[r][i]]] = rd();
ck_b += key_s[sb[b[r][i]]];
}
while(ck_a!=ck_b){
for(int i=0;i<3;i++){
ck_a -= key_s[sa[a[l][i]]];
sa[a[l][i]] = sa[a[l][i]]-key_pos[l];
if(key_s.find(sa[a[l][i]]) == key_s.end()) key_s[sa[a[l][i]]] = rd();
ck_a += key_s[sa[a[l][i]]];
ck_b -= key_s[sb[b[l][i]]];
sb[b[l][i]] = sb[b[l][i]]-key_pos[l];
if(key_s.find(sb[b[l][i]]) == key_s.end()) key_s[sb[b[l][i]]] = rd();
ck_b += key_s[sb[b[l][i]]];
}
l++;
}
lim[r] = l;
}
for(int i=1;i<=q;i++){
int l,r;cin >> l >> r;
if(lim[r]<=l) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9860kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9852kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9816kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9940kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9952kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9848kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9996kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9864kb
Pretest #9:
score: 5
Accepted
time: 17ms
memory: 9872kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 9920kb
Pretest #11:
score: 5
Accepted
time: 876ms
memory: 89312kb
Pretest #12:
score: 5
Accepted
time: 911ms
memory: 85916kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 10520kb
Pretest #14:
score: 5
Accepted
time: 6ms
memory: 10460kb
Pretest #15:
score: 5
Accepted
time: 103ms
memory: 10516kb
Pretest #16:
score: 5
Accepted
time: 104ms
memory: 10504kb
Pretest #17:
score: 5
Accepted
time: 68ms
memory: 16820kb
Pretest #18:
score: 5
Accepted
time: 60ms
memory: 18572kb
Pretest #19:
score: 5
Accepted
time: 1015ms
memory: 85320kb
Pretest #20:
score: 5
Accepted
time: 927ms
memory: 90104kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9848kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 9816kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 9940kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9932kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 9860kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9940kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 9936kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9984kb
Test #9:
score: 5
Accepted
time: 21ms
memory: 9908kb
Test #10:
score: 5
Accepted
time: 16ms
memory: 9916kb
Test #11:
score: 5
Accepted
time: 902ms
memory: 85908kb
Test #12:
score: 5
Accepted
time: 870ms
memory: 81036kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 10444kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 10484kb
Test #15:
score: 5
Accepted
time: 108ms
memory: 10652kb
Test #16:
score: 5
Accepted
time: 106ms
memory: 10476kb
Test #17:
score: 5
Accepted
time: 74ms
memory: 20896kb
Test #18:
score: 5
Accepted
time: 51ms
memory: 20284kb
Test #19:
score: 5
Accepted
time: 1002ms
memory: 83924kb
Test #20:
score: 5
Accepted
time: 955ms
memory: 89248kb
Extra Test:
score: 0
Extra Test Passed