QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#496664#9155. 集合wsc2008100 ✓117ms32548kbC++141.9kb2024-07-28 14:24:582024-07-28 14:24:58

Judging History

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

  • [2024-07-28 14:24:58]
  • 评测
  • 测评结果:100
  • 用时:117ms
  • 内存:32548kb
  • [2024-07-28 14:24:58]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll 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*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=6e5+9;
ll n,m,q,a[N][3],b[N][3],tor[N];
ull ha,hb,sum1a[N],sum1b[N];
ull H(ull x){
    return x*x*x*496712437+x*x*23423467+x*938265+13467667;
}
void Adda(ll p,ll v){
    ha-=H(sum1a[v]);
    sum1a[v]+=H(p);
    ha+=H(sum1a[v]);
}
void Addb(ll p,ll v){
    hb-=H(sum1b[v]);
    sum1b[v]+=H(p);
    hb+=H(sum1b[v]);
}
void Dela(ll p,ll v){
    ha-=H(sum1a[v]);
    sum1a[v]-=H(p);
    ha+=H(sum1a[v]);
}
void Delb(ll p,ll v){
    hb-=H(sum1b[v]);
    sum1b[v]-=H(p);
    hb+=H(sum1b[v]);
}
void Add(ll p){
    rep(i,0,2)Adda(p,a[p][i]);
    rep(i,0,2)Addb(p,b[p][i]);
}
void Del(ll p){
    rep(i,0,2)Dela(p,a[p][i]);
    rep(i,0,2)Delb(p,b[p][i]);
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read(),q=read();
    rep(i,1,n){
        rep(j,0,2)a[i][j]=read();
    }
    rep(i,1,n){
        rep(j,0,2)b[i][j]=read();
    }
    rep(i,1,m){
        sum1a[i]=sum1b[i]=0;
        ha+=H(0),hb+=H(0);
    }
    ll r=0;
    rep(l,1,n){
        if(r<l)r=l,Add(l);
        while(ha==hb){
            r++;
            if(r>n)break;
            Add(r);
        }
        if(r<=n)Del(r);
        r--;
        tor[l]=r;
        Del(l);
    }
    while(q--){
        ll l=read(),r=read();
        if(tor[l]>=r)puts("Yes");
        else puts("No");
    }
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 40ms
memory: 23332kb

Pretest #12:

score: 5
Accepted
time: 40ms
memory: 20492kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 6ms
memory: 14816kb

Pretest #19:

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

Pretest #20:

score: 5
Accepted
time: 117ms
memory: 32548kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 46ms
memory: 21500kb

Test #12:

score: 5
Accepted
time: 38ms
memory: 21664kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 47ms
memory: 10112kb

Test #16:

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

Test #17:

score: 5
Accepted
time: 6ms
memory: 14332kb

Test #18:

score: 5
Accepted
time: 6ms
memory: 10720kb

Test #19:

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

Test #20:

score: 5
Accepted
time: 111ms
memory: 27148kb

Extra Test:

score: 0
Extra Test Passed