QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492079#9155. 集合Dawnq#100 ✓477ms20188kbC++141.3kb2024-07-26 09:04:512024-07-26 09:04:52

Judging History

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

  • [2024-07-26 09:04:52]
  • 评测
  • 测评结果:100
  • 用时:477ms
  • 内存:20188kb
  • [2024-07-26 09:04:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5;
int n,m,q,a[N][3],b[N][3],R[N];
ull s1,s2,val,d[N],A[N*3],B[N*3];
mt19937_64 rnd(time(0));
inline ull calc(ull x){return x<<=5,x>>=7,x^=val,x<<=3,x>>=11;}
inline void add(int x){
    if(x>n)return;
    for(int i:a[x])s1-=calc(A[i]),A[i]+=d[x],s1+=calc(A[i]);
    for(int i:b[x])s2-=calc(B[i]),B[i]+=d[x],s2+=calc(B[i]);
}
inline void del(int x){
    if(x>n)return;
    for(int i:a[x])s1-=calc(A[i]),A[i]-=d[x],s1+=calc(A[i]);
    for(int i:b[x])s2-=calc(B[i]),B[i]-=d[x],s2+=calc(B[i]);
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;++i){
        for(int j=0;j<3;++j)cin>>a[i][j];
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<3;++j)cin>>b[i][j];
    }
    for(int i=1;i<=n;++i)R[i]=n;
    for(int op=1;op<=50;++op){
        val=rnd(),s1=s2=0;
        for(int i=1;i<=n;++i)d[i]=rnd(),A[i]=B[i]=0;
        add(1);
        for(int i=1,j=1;i<=n;++i){
            while(j<=n&&s1==s2)++j,add(j);
            R[i]=min(R[i],j-1),del(i);
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(R[l]>=r)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 11876kb

Pretest #4:

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

Pretest #5:

score: 5
Accepted
time: 1ms
memory: 11876kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 11972kb

Pretest #7:

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

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 11880kb

Pretest #9:

score: 5
Accepted
time: 16ms
memory: 11884kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 306ms
memory: 17992kb

Pretest #12:

score: 5
Accepted
time: 284ms
memory: 20184kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 100ms
memory: 12020kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 32ms
memory: 12440kb

Pretest #19:

score: 5
Accepted
time: 385ms
memory: 16096kb

Pretest #20:

score: 5
Accepted
time: 472ms
memory: 20032kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

score: 5
Accepted
time: 1ms
memory: 11948kb

Test #6:

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

Test #7:

score: 5
Accepted
time: 1ms
memory: 11824kb

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 312ms
memory: 18124kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 5
Accepted
time: 29ms
memory: 14172kb

Test #18:

score: 5
Accepted
time: 32ms
memory: 12440kb

Test #19:

score: 5
Accepted
time: 384ms
memory: 20168kb

Test #20:

score: 5
Accepted
time: 477ms
memory: 20188kb

Extra Test:

score: 0
Extra Test Passed