QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#494288#9155. 集合_FJqwq100 ✓266ms43004kbC++141.5kb2024-07-27 15:03:092024-07-27 15:03:09

Judging History

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

  • [2024-07-27 15:03:09]
  • 评测
  • 测评结果:100
  • 用时:266ms
  • 内存:43004kb
  • [2024-07-27 15:03:09]
  • 提交

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