QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#494288 | #9155. 集合 | _FJqwq | 100 ✓ | 266ms | 43004kb | C++14 | 1.5kb | 2024-07-27 15:03:09 | 2024-07-27 15:03:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005,M=600005,L=1000005;
int n,m,q,to=1;
int a1[N],a2[N],a3[N];
int b1[N],b2[N],b3[N];
int v1[M],v2[M],b[N];
ll m1,m2,m3,m4,v3[M],v4[M];
mt19937 rnd(555301);
struct node{int l,id;};
vector<node>v[N];
bool vis[L];
void del1(int x){m1-=v1[x];m3^=v3[x];}
void del2(int x){m2-=v2[x];m4^=v4[x];}
void ins1(int x){m1+=v1[x];m3^=v3[x];}
void ins2(int x){m2+=v2[x];m4^=v4[x];}
void qwq1(int x,int y){del1(x);v1[x]^=y;v3[x]+=y;ins1(x);}
void qwq2(int x,int y){del2(x);v2[x]^=y;v4[x]+=y;ins2(x);}
void pwp1(int x,int y){del1(x);v1[x]^=y;v3[x]-=y;ins1(x);}
void pwp2(int x,int y){del2(x);v2[x]^=y;v4[x]-=y;ins2(x);}
int main(){
// freopen("ex_4.in","r",stdin);
// freopen("ex_4.out","w",stdout);
srand(time(0));
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d%d%d",&a1[i],&a2[i],&a3[i]);
for(int i=1;i<=n;i++) scanf("%d%d%d",&b1[i],&b2[i],&b3[i]);
for(int i=1;i<=n;i++) b[i]=rnd();
for(int i=1,x,y;i<=q;i++){
scanf("%d%d",&x,&y);
v[y].push_back(node{x,i});
}
for(int i=1;i<=n;i++){
qwq1(a1[i],b[i]);
qwq1(a2[i],b[i]);
qwq1(a3[i],b[i]);
qwq2(b1[i],b[i]);
qwq2(b2[i],b[i]);
qwq2(b3[i],b[i]);
while((to<i)&&((m1!=m2)||(m3!=m4))){
pwp1(a1[to],b[to]);
pwp1(a2[to],b[to]);
pwp1(a3[to],b[to]);
pwp2(b1[to],b[to]);
pwp2(b2[to],b[to]);
pwp2(b3[to],b[to]);
to++;
}
for(node e:v[i])
vis[e.id]=(to<=e.l);
}
for(int i=1;i<=q;i++)
if(vis[i]) puts("Yes");
else puts("No");
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 16004kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 18096kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 14724kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 15140kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 18036kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 14648kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 16068kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 14740kb
Pretest #9:
score: 5
Accepted
time: 24ms
memory: 18176kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 19932kb
Pretest #11:
score: 5
Accepted
time: 81ms
memory: 22392kb
Pretest #12:
score: 5
Accepted
time: 70ms
memory: 23852kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 16196kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 16576kb
Pretest #15:
score: 5
Accepted
time: 106ms
memory: 29464kb
Pretest #16:
score: 5
Accepted
time: 118ms
memory: 29308kb
Pretest #17:
score: 5
Accepted
time: 4ms
memory: 14836kb
Pretest #18:
score: 5
Accepted
time: 10ms
memory: 17324kb
Pretest #19:
score: 5
Accepted
time: 241ms
memory: 32612kb
Pretest #20:
score: 5
Accepted
time: 258ms
memory: 43004kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 16268kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 16052kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 16060kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 14960kb
Test #5:
score: 5
Accepted
time: 3ms
memory: 18232kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 16116kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 16016kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 14960kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 16700kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 20220kb
Test #11:
score: 5
Accepted
time: 81ms
memory: 19756kb
Test #12:
score: 5
Accepted
time: 86ms
memory: 19604kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 18220kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 16596kb
Test #15:
score: 5
Accepted
time: 106ms
memory: 27896kb
Test #16:
score: 5
Accepted
time: 118ms
memory: 28220kb
Test #17:
score: 5
Accepted
time: 5ms
memory: 16356kb
Test #18:
score: 5
Accepted
time: 10ms
memory: 19104kb
Test #19:
score: 5
Accepted
time: 247ms
memory: 32736kb
Test #20:
score: 5
Accepted
time: 266ms
memory: 42808kb
Extra Test:
score: 0
Extra Test Passed