QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499507#9155. 集合eastcloud#100 ✓455ms112856kbC++202.0kb2024-07-31 15:03:052024-07-31 15:03:06

Judging History

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

  • [2024-07-31 15:03:06]
  • 评测
  • 测评结果:100
  • 用时:455ms
  • 内存:112856kb
  • [2024-07-31 15:03:05]
  • 提交

answer

#include<bits/stdc++.h>

#define ll unsigned long long
#define pi pair<ll,ll>
#define fi first
#define se second
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mem(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define vi vector<ll> 
#define arr array
#define pb push_back
#define mp make_pair

using namespace std;

#define N 2000005

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

ll p[N],a[N][4],b[N][4],val[N];
ll res[N];

vector<pi> Q[N];
unordered_map<ll,ll> t;

ll sum=0,cnt=0;
mt19937_64 rnd(114514);

void add(ll v,ll pos){cnt++;
    if(t[val[v]]==1)sum--;
    if(t[val[v]]==0)sum++;
    t[val[v]]--;
    val[v]^=p[pos];
    t[val[v]]++;
    if(t[val[v]]==0)sum--;
    if(t[val[v]]==1)sum++;
}
void del(ll v,ll pos){cnt++;
    if(t[val[v]]==0)sum++;
    if(t[val[v]]==-1)sum--;
    t[val[v]]++;
    val[v]^=p[pos];
    t[val[v]]--;
    if(t[val[v]]==0)sum--;
    if(t[val[v]]==-1)sum++;
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    ll n=read(),m=read(),q=read();
    for(ll i=1;i<=n;i++)p[i]=rnd();
    for(ll i=1;i<=n;i++)for(ll j=1;j<=3;j++)a[i][j]=read();
    for(ll i=1;i<=n;i++)for(ll j=1;j<=3;j++)b[i][j]=read();
    for(ll i=1;i<=q;i++){
        ll l=read(),r=read();
        Q[r].push_back(mp(i,l));
    }
    ll l=1;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=3;j++)add(a[i][j],i),del(b[i][j]+m,i);
        while(sum!=0){
            for(ll j=1;j<=3;j++)add(a[l][j],l),del(b[l][j]+m,l);
            l++;
        }
        if(clock()*1.0/CLOCKS_PER_SEC*1000>900){assert(l<=i);break;}
        for(auto [id,L]:Q[i])if(L>=l)res[id]=1;
    }
    for(ll i=1;i<=q;i++){
        if(res[i])printf("Yes\n");
        else printf("No\n");
    }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 286ms
memory: 80524kb

Pretest #12:

score: 5
Accepted
time: 279ms
memory: 80324kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 58ms
memory: 41872kb

Pretest #16:

score: 5
Accepted
time: 74ms
memory: 41924kb

Pretest #17:

score: 5
Accepted
time: 25ms
memory: 18332kb

Pretest #18:

score: 5
Accepted
time: 27ms
memory: 17424kb

Pretest #19:

score: 5
Accepted
time: 441ms
memory: 107692kb

Pretest #20:

score: 5
Accepted
time: 455ms
memory: 108472kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 273ms
memory: 78504kb

Test #12:

score: 5
Accepted
time: 279ms
memory: 78424kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 64ms
memory: 42100kb

Test #16:

score: 5
Accepted
time: 60ms
memory: 43908kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 450ms
memory: 104468kb

Test #20:

score: 5
Accepted
time: 429ms
memory: 112856kb

Extra Test:

score: 0
Extra Test Passed