QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526238#9155. 集合lefy100 ✓275ms20464kbC++141.3kb2024-08-21 12:32:572024-08-21 12:32:59

Judging History

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

  • [2024-08-21 12:32:59]
  • 评测
  • 测评结果:100
  • 用时:275ms
  • 内存:20464kb
  • [2024-08-21 12:32:57]
  • 提交

answer

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=2e5+10,M=6e5+10;
int a[3][N],b[3][N];
ull to[N],A[M],B[M];
mt19937 rd(time(0));
int pos[N];
int add(int p){
    for(int i=0;i<3;i++)A[a[i][p]]+=to[p],B[b[i][p]]+=to[p];
    vector<int>t1,t2;
    for(int i=0;i<3;i++){
        t1.push_back(A[a[i][p]]),t2.push_back(B[b[i][p]]);
        // cout<<A[a[i][p]]<<" "<<B[b[i][p]]<<"\n";
    }
    sort(t1.begin(),t1.end());sort(t2.begin(),t2.end());
    for(int i=0;i<3;i++)if(t1[i]^t2[i])return 1;
    return 0;
}
void del(int p){
    for(int i=0;i<3;i++)A[a[i][p]]-=to[p],B[b[i][p]]-=to[p];
}
int main() {
    // freopen("ex_4.in","r",stdin);
    // freopen("3.out","w",stdout);
    int n,m,Q;scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;i++){
        to[i]=rd();
        for(int j=0;j<3;j++)scanf("%d",&a[j][i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)scanf("%d",&b[j][i]);
    }
    for(int i=1,r=0;i<=n;i++){
        while(r<n){
            r++;
            if(r>n)break;
            if(add(r)){
                del(r);r--;
                break;
            }
        }
        pos[i]=r;
        del(i);
    }
    while(Q--){
        int l,r;scanf("%d%d",&l,&r);
        if(pos[l]>=r)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 14328kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 14016kb

Pretest #3:

score: 5
Accepted
time: 2ms
memory: 12064kb

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 14100kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 14080kb

Pretest #6:

score: 5
Accepted
time: 2ms
memory: 14336kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 14076kb

Pretest #8:

score: 5
Accepted
time: 2ms
memory: 12068kb

Pretest #9:

score: 5
Accepted
time: 24ms
memory: 14104kb

Pretest #10:

score: 5
Accepted
time: 21ms
memory: 14108kb

Pretest #11:

score: 5
Accepted
time: 134ms
memory: 13576kb

Pretest #12:

score: 5
Accepted
time: 132ms
memory: 15172kb

Pretest #13:

score: 5
Accepted
time: 3ms
memory: 11996kb

Pretest #14:

score: 5
Accepted
time: 0ms
memory: 12036kb

Pretest #15:

score: 5
Accepted
time: 116ms
memory: 14352kb

Pretest #16:

score: 5
Accepted
time: 120ms
memory: 14100kb

Pretest #17:

score: 5
Accepted
time: 10ms
memory: 14124kb

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 14312kb

Pretest #19:

score: 5
Accepted
time: 250ms
memory: 16084kb

Pretest #20:

score: 5
Accepted
time: 275ms
memory: 20240kb

Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 12284kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 14312kb

Test #3:

score: 5
Accepted
time: 2ms
memory: 11968kb

Test #4:

score: 5
Accepted
time: 2ms
memory: 14020kb

Test #5:

score: 5
Accepted
time: 0ms
memory: 12284kb

Test #6:

score: 5
Accepted
time: 2ms
memory: 12256kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 12064kb

Test #8:

score: 5
Accepted
time: 2ms
memory: 12292kb

Test #9:

score: 5
Accepted
time: 25ms
memory: 14016kb

Test #10:

score: 5
Accepted
time: 20ms
memory: 11996kb

Test #11:

score: 5
Accepted
time: 127ms
memory: 16104kb

Test #12:

score: 5
Accepted
time: 122ms
memory: 16100kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 12268kb

Test #14:

score: 5
Accepted
time: 3ms
memory: 12024kb

Test #15:

score: 5
Accepted
time: 116ms
memory: 14304kb

Test #16:

score: 5
Accepted
time: 125ms
memory: 14328kb

Test #17:

score: 5
Accepted
time: 10ms
memory: 12324kb

Test #18:

score: 5
Accepted
time: 14ms
memory: 14648kb

Test #19:

score: 5
Accepted
time: 243ms
memory: 13408kb

Test #20:

score: 5
Accepted
time: 261ms
memory: 20464kb

Extra Test:

score: 0
Extra Test Passed