QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492371#9155. 集合fqoi100 ✓259ms42888kbC++141.5kb2024-07-26 11:42:382024-07-26 11:42:39

Judging History

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

  • [2024-07-26 11:42:39]
  • 评测
  • 测评结果:100
  • 用时:259ms
  • 内存:42888kb
  • [2024-07-26 11:42:38]
  • 提交

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