QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498684#9155. 集合cjwen100 ✓151ms20852kbC++142.6kb2024-07-30 17:47:192024-07-30 17:47:22

Judging History

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

  • [2024-07-30 17:47:22]
  • 评测
  • 测评结果:100
  • 用时:151ms
  • 内存:20852kb
  • [2024-07-30 17:47:19]
  • 提交

answer

#include<bits/stdc++.h>

#define mo(x, y) ((((x)%P##y)+P##y)%P##y)
#define qmi2(x) (pb3[x/L]*pb2[x%L]%P2)

using namespace std;

void read(int &x){
    x = 0;
    char c = getchar();
    while(c < '0'|| c > '9') c = getchar();
    while('0' <= c && c <= '9'){
        x = x*10+c-'0';
        c = getchar();
    }
}

long long qmi(long long qa, long long qb, long long qc){
    long long qans = 1;
    while(qb){
        if(qb & 1) qans = qans * qa % qc;
        qa = qa * qa % qc;
        qb >>= 1;
    }
    return qans;
}

const int N = 2e5 + 5, M = 6e5 + 5, Q = 1e6 + 5;
const int B1 = 131, P1 = 998244353;
const int B2 = 13331, P2 = 1e9+7;
const int L = 5e4;

int n, m, q;
int a[N][3];
int b[N][3];
int maxl[N];

long long pha[M], phb[M];
long long hsha, hshb;

long long pb1[N];
long long pb2[L], pb3[L];

void add(int x){
    for(int i = 0; i < 3; i++){
        hsha = mo(hsha-qmi2(pha[a[x][i]]), 2);
        pha[a[x][i]] = mo(pha[a[x][i]]+pb1[x], 1);
        hsha = mo(hsha+qmi2(pha[a[x][i]]), 2);
        hshb = mo(hshb-qmi2(phb[b[x][i]]), 2);
        phb[b[x][i]] = mo(phb[b[x][i]]+pb1[x], 1);
        hshb = mo(hshb+qmi2(phb[b[x][i]]), 2);
    }
}

void del(int x){
    for(int i = 0; i < 3; i++){
        hsha = mo(hsha-qmi2(pha[a[x][i]]), 2);
        pha[a[x][i]] = mo(pha[a[x][i]]-pb1[x], 1);
        hsha = mo(hsha+qmi2(pha[a[x][i]]), 2);
        hshb = mo(hshb-qmi2(phb[b[x][i]]), 2);
        phb[b[x][i]] = mo(phb[b[x][i]]-pb1[x], 1);
        hshb = mo(hshb+qmi2(phb[b[x][i]]), 2);
    }
}

bool check(){
    return hsha == hshb;
}

int main(){

    pb1[0] = 1;
    for(int i = 1; i < N; i++){
        pb1[i] = pb1[i-1] * B1 % P1;
    }
    pb2[0] = 1;
    for(int i = 1; i < L; i++){
        pb2[i] = pb2[i-1] * B2 % P2;
    }
    pb3[0] = 1; pb3[1] = pb2[L-1] * B2 % P2;
    for(int i = 1; i < L; i++){
        pb3[i] = pb3[i-1] * pb3[1] % P2;
    }

    read(n); read(m); read(q);
    for(int i = 1; i <= n; i++){
        read(a[i][0]); read(a[i][1]); read(a[i][2]);
    }
    for(int i = 1; i <= n; i++){
        read(b[i][0]); read(b[i][1]); read(b[i][2]);
    }

    hsha = hshb = m;

    for(int l = 1, r = 0; l <= n; ){
        while(r < n){
            add(++r);
            if(!check()){
                del(r--);
                break;
            }
        }
        maxl[l] = r;
        del(l++);
    }

    int x = 0, y = 0;
    while(q--){
        read(x); read(y);
        if(y <= maxl[x]){
            puts("Yes");
        }else{
            puts("No");
        }
    }

    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 7ms
memory: 13344kb

Pretest #10:

score: 5
Accepted
time: 11ms
memory: 11060kb

Pretest #11:

score: 5
Accepted
time: 82ms
memory: 12684kb

Pretest #12:

score: 5
Accepted
time: 85ms
memory: 12692kb

Pretest #13:

score: 5
Accepted
time: 4ms
memory: 10916kb

Pretest #14:

score: 5
Accepted
time: 4ms
memory: 14032kb

Pretest #15:

score: 5
Accepted
time: 41ms
memory: 11124kb

Pretest #16:

score: 5
Accepted
time: 51ms
memory: 13860kb

Pretest #17:

score: 5
Accepted
time: 11ms
memory: 10900kb

Pretest #18:

score: 5
Accepted
time: 12ms
memory: 11644kb

Pretest #19:

score: 5
Accepted
time: 131ms
memory: 12612kb

Pretest #20:

score: 5
Accepted
time: 137ms
memory: 20748kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 11ms
memory: 10468kb

Test #10:

score: 5
Accepted
time: 11ms
memory: 11052kb

Test #11:

score: 5
Accepted
time: 85ms
memory: 12672kb

Test #12:

score: 5
Accepted
time: 80ms
memory: 12624kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 4ms
memory: 13552kb

Test #15:

score: 5
Accepted
time: 52ms
memory: 13908kb

Test #16:

score: 5
Accepted
time: 41ms
memory: 14028kb

Test #17:

score: 5
Accepted
time: 11ms
memory: 11012kb

Test #18:

score: 5
Accepted
time: 12ms
memory: 14148kb

Test #19:

score: 5
Accepted
time: 143ms
memory: 12576kb

Test #20:

score: 5
Accepted
time: 151ms
memory: 20852kb

Extra Test:

score: 0
Extra Test Passed