QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488698#9155. 集合zxh923100 ✓877ms32836kbC++141.3kb2024-07-24 14:13:112024-07-24 14:13:11

Judging History

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

  • [2024-07-24 14:13:11]
  • 评测
  • 测评结果:100
  • 用时:877ms
  • 内存:32836kb
  • [2024-07-24 14:13:11]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define N 600005
using namespace std;
int n,m,q,a[N][3],b[N][3];
ull nowa[N],nowb[N],suma,sumb,p[N];
int ri[N];//使[i,j]合法的最靠右的j
ull get_rnd(ull x){
	return x*x*x;//随便变换一下
}
void work(int id,int type){
	for(int j=0;j<3;j++){
		ull i=a[id][j];
		suma-=get_rnd(nowa[i]);//把原来的值减掉
		nowa[i]+=type*p[id];//看情况加上或减去这个位置的哈希值
		suma+=get_rnd(nowa[i]);//加上现在的值
	}
	for(int j=0;j<3;j++){//这里同理
		ull i=b[id][j];
		sumb-=get_rnd(nowb[i]);
		nowb[i]+=type*p[id];
		sumb+=get_rnd(nowb[i]);
	}
}
signed main(){
	srand(time(0));
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++){
			cin>>b[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		ri[i]=n;
	}
	for(int i=1;i<=n;i++){
		p[i]=rand()*rand()+923;
	}
	work(1,1);
	for(int i=1,j=1;i<=n;i++){
		while(j<=n&&suma==sumb){//如果当前仍然合法
			j++;
			if(j>n)break;
			work(j,1);
		}
		ri[i]=min(ri[i],j-1);
		work(i,-1);//i要右移,所以撤掉这一位的贡献
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<(ri[l]>=r?"Yes\n":"No\n");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 9968kb

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 92ms
memory: 9948kb

Pretest #10:

score: 5
Accepted
time: 75ms
memory: 9776kb

Pretest #11:

score: 5
Accepted
time: 220ms
memory: 21712kb

Pretest #12:

score: 5
Accepted
time: 244ms
memory: 24996kb

Pretest #13:

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

Pretest #14:

score: 5
Accepted
time: 5ms
memory: 9960kb

Pretest #15:

score: 5
Accepted
time: 523ms
memory: 9860kb

Pretest #16:

score: 5
Accepted
time: 480ms
memory: 11988kb

Pretest #17:

score: 5
Accepted
time: 17ms
memory: 13908kb

Pretest #18:

score: 5
Accepted
time: 22ms
memory: 13108kb

Pretest #19:

score: 5
Accepted
time: 726ms
memory: 24724kb

Pretest #20:

score: 5
Accepted
time: 844ms
memory: 32836kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 107ms
memory: 9908kb

Test #10:

score: 5
Accepted
time: 103ms
memory: 9924kb

Test #11:

score: 5
Accepted
time: 256ms
memory: 21624kb

Test #12:

score: 5
Accepted
time: 255ms
memory: 21620kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 508ms
memory: 9984kb

Test #16:

score: 5
Accepted
time: 498ms
memory: 9892kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 23ms
memory: 15100kb

Test #19:

score: 5
Accepted
time: 794ms
memory: 25076kb

Test #20:

score: 5
Accepted
time: 877ms
memory: 30708kb

Extra Test:

score: 0
Extra Test Passed