QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492371 | #9155. 集合 | fqoi | 100 ✓ | 259ms | 42888kb | C++14 | 1.5kb | 2024-07-26 11:42:38 | 2024-07-26 11:42:39 |
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: 18236kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 16552kb
Pretest #3:
score: 5
Accepted
time: 3ms
memory: 18232kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 16152kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 18040kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 15976kb
Pretest #7:
score: 5
Accepted
time: 3ms
memory: 16100kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 15140kb
Pretest #9:
score: 5
Accepted
time: 11ms
memory: 18524kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 16824kb
Pretest #11:
score: 5
Accepted
time: 75ms
memory: 19600kb
Pretest #12:
score: 5
Accepted
time: 70ms
memory: 23824kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 18252kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 16128kb
Pretest #15:
score: 5
Accepted
time: 115ms
memory: 29856kb
Pretest #16:
score: 5
Accepted
time: 116ms
memory: 28388kb
Pretest #17:
score: 5
Accepted
time: 5ms
memory: 16520kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 17560kb
Pretest #19:
score: 5
Accepted
time: 243ms
memory: 34828kb
Pretest #20:
score: 5
Accepted
time: 259ms
memory: 42888kb
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 14880kb
Test #2:
score: 5
Accepted
time: 3ms
memory: 14916kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 18232kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 15012kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 14912kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 16400kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 18040kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 18100kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 18376kb
Test #10:
score: 5
Accepted
time: 23ms
memory: 20280kb
Test #11:
score: 5
Accepted
time: 80ms
memory: 19756kb
Test #12:
score: 5
Accepted
time: 75ms
memory: 23776kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 14660kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 14880kb
Test #15:
score: 5
Accepted
time: 119ms
memory: 29636kb
Test #16:
score: 5
Accepted
time: 117ms
memory: 28208kb
Test #17:
score: 5
Accepted
time: 8ms
memory: 18020kb
Test #18:
score: 5
Accepted
time: 7ms
memory: 18912kb
Test #19:
score: 5
Accepted
time: 241ms
memory: 30760kb
Test #20:
score: 5
Accepted
time: 254ms
memory: 42788kb
Extra Test:
score: 0
Extra Test Passed