QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509120#9155. 集合jager59100 ✓160ms53216kbC++172.3kb2024-08-08 10:32:242024-08-08 10:32:25

Judging History

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

  • [2024-08-08 10:32:25]
  • 评测
  • 测评结果:100
  • 用时:160ms
  • 内存:53216kb
  • [2024-08-08 10:32:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const long long inf=1e13;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
mt19937_64 orz(113132);
int n,m,q,a[N][3],b[N][3],cnt,ans[N];
long long val[N*3][2],vvv[N];
const int mod = 4e6+7;
struct htable{
    int head[mod],etot;
    struct edge{
        int nxt,val;
        long long v;
    }e[mod];
    inline void insert(long long x,int op){
        // cerr<<"!"<<x<<' '<<op<<endl;
        int p = x%mod;
        for(int i = head[p];i;i=e[i].nxt){
            if(e[i].v==x){
                e[i].val+=op;
                if(e[i].val==1&&op==1)cnt++;
                else if(e[i].val==-1&&op==-1)cnt++;
                else if(!e[i].val)cnt--;
                return;
            }
        }
        e[++etot]={head[p],op,x};cnt++;head[p]=etot;
    }
}mp;
inline void add(int x,long long v,int op,int k){
    if(val[x][op]){
        if(op==1)mp.insert(val[x][op],-1);
        else mp.insert(val[x][op],1);
    }
    val[x][op]+=v*k;
    
    if(val[x][op]){
        if(op==1)mp.insert(val[x][op],1);
        else mp.insert(val[x][op],-1);
    }
    // cerr<<"??"<<x<<' '<<op<<' '<<val[x][op]<<' '<<cnt<<endl;
}
int main(){
    n=read(),m=read(),q=read();
    for(int i = 1;i<=n;i++)a[i][0]=read(),a[i][1]=read(),a[i][2]=read(),vvv[i]=orz()%inf+1;
    for(int i = 1;i<=n;i++)b[i][0]=read(),b[i][1]=read(),b[i][2]=read();
    for(int l = 1,r=0;l<=n;l++){
        while(!cnt && r<n){
            // cerr<<l<<' '<<r<<endl;
            r++;
            for(int j = 0;j<3;j++)add(a[r][j],vvv[r],0,1),add(b[r][j],vvv[r],1,1);
            // cerr<<l<<' '<<r<<' '<<cnt<<endl;
            if(cnt){
                // cerr<<l<<' '<<r<<endl;
                for(int j = 0;j<3;j++)add(a[r][j],vvv[r],0,-1),add(b[r][j],vvv[r],1,-1);
                r--;
                break;
            }
        }
        ans[l]=r;
        for(int j = 0;j<3;j++)add(a[l][j],vvv[l],0,-1),add(b[l][j],vvv[l],1,-1);
    }
    while(q--){
        int l=read(),r=read();
        if(ans[l]>=r)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 92ms
memory: 51128kb

Pretest #12:

score: 5
Accepted
time: 87ms
memory: 49052kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 49ms
memory: 24468kb

Pretest #17:

score: 5
Accepted
time: 8ms
memory: 30632kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 147ms
memory: 47008kb

Pretest #20:

score: 5
Accepted
time: 160ms
memory: 51168kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 89ms
memory: 49080kb

Test #12:

score: 5
Accepted
time: 81ms
memory: 47028kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 49ms
memory: 26964kb

Test #16:

score: 5
Accepted
time: 53ms
memory: 24380kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 159ms
memory: 46964kb

Test #20:

score: 5
Accepted
time: 152ms
memory: 53216kb

Extra Test:

score: 0
Extra Test Passed