QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506451#9155. 集合1048576100 ✓875ms32880kbC++141.3kb2024-08-05 17:34:502024-08-05 17:34:52

Judging History

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

  • [2024-08-05 17:34:52]
  • 评测
  • 测评结果:100
  • 用时:875ms
  • 内存:32880kb
  • [2024-08-05 17:34:50]
  • 提交

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: 1ms
memory: 9912kb

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 102ms
memory: 9812kb

Pretest #11:

score: 5
Accepted
time: 240ms
memory: 21648kb

Pretest #12:

score: 5
Accepted
time: 216ms
memory: 24660kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 476ms
memory: 9832kb

Pretest #16:

score: 5
Accepted
time: 460ms
memory: 9872kb

Pretest #17:

score: 5
Accepted
time: 12ms
memory: 10004kb

Pretest #18:

score: 5
Accepted
time: 15ms
memory: 15160kb

Pretest #19:

score: 5
Accepted
time: 757ms
memory: 22380kb

Pretest #20:

score: 5
Accepted
time: 835ms
memory: 32880kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 225ms
memory: 21580kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 496ms
memory: 10080kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 808ms
memory: 23152kb

Test #20:

score: 5
Accepted
time: 875ms
memory: 31432kb

Extra Test:

score: 0
Extra Test Passed