QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527123#9155. 集合sumi007#100 ✓1015ms90104kbC++141.8kb2024-08-22 10:30:532024-08-22 10:30:53

Judging History

你现在查看的是最新测评结果

  • [2024-08-22 10:30:53]
  • 评测
  • 测评结果:100
  • 用时:1015ms
  • 内存:90104kb
  • [2024-08-22 10:30:53]
  • 提交

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