QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487453#9155. 集合TulipeNoire100 ✓168ms42200kbC++142.0kb2024-07-22 21:52:002024-07-22 21:52:00

Judging History

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

  • [2024-07-22 21:52:00]
  • 评测
  • 测评结果:100
  • 用时:168ms
  • 内存:42200kb
  • [2024-07-22 21:52:00]
  • 提交

answer

#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
using namespace std;
mt19937_64 myrand(time(NULL));
using LL=long long;
using uint=unsigned;
using pii=pair<int,int>;
using vi=vector<int>;
using vp=vector<pii>;
template<typename T>inline void read(T&t){
    t=0;
    char c=getchar();
    int f=1;
    while (!isdigit(c)) f=c=='-'?-f:f,c=getchar();
    while (isdigit(c)) t=(t<<3)+(t<<1)+c-'0',c=getchar();
    t*=f;
    return;
}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t),read(args...);}
template<typename T>void write(T x){if(x>=10)write(x/10);putchar(x%10+'0');return;}
template<typename T>inline bool chkmax(T&x,T y){return y>x?(x=y,1):0;}
template<typename T>inline bool chkmin(T&x,T y){return y<x?(x=y,1):0;}

const int N=200005;
int n,m,q,a[N][3],b[N][3],maxr[N];
LL val[N][3],nowa[N*3][3],nowb[N*3][3],suma[3],sumb[3];
inline void update(int x) {
    for (int i=0;i<3;i++) {
        for (int j=0;j<3;j++) {
            suma[j]-=nowa[a[x][i]][j],sumb[j]-=nowb[b[x][i]][j];
            nowa[a[x][i]][j]^=val[x][j];
            nowb[b[x][i]][j]^=val[x][j];
            suma[j]+=nowa[a[x][i]][j],sumb[j]+=nowb[b[x][i]][j];
        }
    }
}
int main() {
    read(n,m,q);
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) read(a[i][j]);
        for (int j=0;j<3;j++) val[i][j]=myrand()&((1ll<<40)-1);
    }
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) read(b[i][j]);
    }
    int r=0;
    for (int i=1;i<=n;i++) {
        while (1) {
            if (r<n) {
                update(++r);
                if (suma[0]!=sumb[0]||suma[1]!=sumb[1]||suma[2]!=sumb[2]) {
                    update(r--);
                    break;
                }
            } else break;
        }
        maxr[i]=r;
        update(i);
    }
    while (q--) {
        int l,r;
        scanf("%d %d",&l,&r);
        if (r<=maxr[l]) puts("Yes");
        else puts("No");
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 22ms
memory: 10044kb

Pretest #10:

score: 5
Accepted
time: 22ms
memory: 11964kb

Pretest #11:

score: 5
Accepted
time: 48ms
memory: 14464kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 104ms
memory: 11900kb

Pretest #16:

score: 5
Accepted
time: 115ms
memory: 10224kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 154ms
memory: 14908kb

Pretest #20:

score: 5
Accepted
time: 168ms
memory: 42200kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 23ms
memory: 10048kb

Test #10:

score: 5
Accepted
time: 19ms
memory: 10072kb

Test #11:

score: 5
Accepted
time: 50ms
memory: 14860kb

Test #12:

score: 5
Accepted
time: 45ms
memory: 13944kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 103ms
memory: 11952kb

Test #16:

score: 5
Accepted
time: 113ms
memory: 12340kb

Test #17:

score: 5
Accepted
time: 5ms
memory: 12076kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 138ms
memory: 15748kb

Test #20:

score: 5
Accepted
time: 162ms
memory: 42172kb

Extra Test:

score: 0
Extra Test Passed