QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#496557#9155. 集合LiWenX#100 ✓1013ms70932kbC++203.4kb2024-07-28 13:10:142024-07-28 13:10:14

Judging History

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

  • [2024-07-28 13:10:14]
  • 评测
  • 测评结果:100
  • 用时:1013ms
  • 内存:70932kb
  • [2024-07-28 13:10:14]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
//#define int long long
#define mp make_pair
using namespace std;
int a[200005][3],b[200005][3];
int n,m,q;
struct Hash{
	int val[200005],inv[200005],seed,mod;
	int quickpow(int a,int b){
		int ret=1;
		while(b){
			if(b&1) ret=1ll*ret*a%mod;
			a=1ll*a*a%mod;
			b>>=1;
		}return ret;
	}
	int t[600005],ha;
	void init(){
		mt19937 rd(seed);
		for(int i=1;i<=n;i++){
			val[i]=rd()%mod;
			inv[i]=quickpow(val[i],mod-2);
		}
		for(int i=1;i<=m;i++) t[i]=1;
	}
	int F(int x){
		return (((1ll*x*911+113)%mod)^12786145)%mod;
	}
	void add(int x,int k){
		ha-=F(t[k]);if(ha<0) ha+=mod;
		t[k]=1ll*t[k]*val[x]%mod;
		ha+=F(t[k]);if(ha>=mod) ha-=mod;
	}
	void del(int x,int k){
		ha-=F(t[k]);if(ha<0) ha+=mod;
		t[k]=1ll*t[k]*inv[x]%mod;
		ha+=F(t[k]);if(ha>=mod) ha-=mod;
	}
}A[5],B[5];
int ans[1000005];
vector<pair<int,int> > vec[200005];
signed main(){
//	freopen("ex_4.in","r",stdin);
//	freopen("solve.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i][0]>>b[i][1]>>b[i][2];
	}
	A[0].mod=B[0].mod=998244353;
	A[0].seed=B[0].seed=210;
	A[0].init(),B[0].init();
	A[1].mod=B[1].mod=1000000123;
	A[1].seed=B[1].seed=123456789;
	A[1].init(),B[1].init();
	A[2].mod=B[2].mod=1000000007;
	A[2].seed=B[2].seed=114;
	A[2].init(),B[2].init();
	A[3].mod=B[3].mod=1000000009;
	A[3].seed=B[3].seed=514;
	A[3].init(),B[3].init();
	A[4].mod=B[4].mod=1145141;
	A[4].seed=B[4].seed=1919;
	A[4].init(),B[4].init();
	for(int i=1;i<=q;i++){
		int l,r;cin>>l>>r;
		vec[l].push_back(mp(r,i));
	}
	int r=0;
	for(int l=1;l<=n;l++){
		while(r+1<=n){
			r++;
			for(int j=0;j<3;j++) A[0].add(r,a[r][j]);
			for(int j=0;j<3;j++) B[0].add(r,b[r][j]);
			for(int j=0;j<3;j++) A[1].add(r,a[r][j]);
			for(int j=0;j<3;j++) B[1].add(r,b[r][j]);
			for(int j=0;j<3;j++) A[2].add(r,a[r][j]);
			for(int j=0;j<3;j++) B[2].add(r,b[r][j]);
			for(int j=0;j<3;j++) A[3].add(r,a[r][j]);
			for(int j=0;j<3;j++) B[3].add(r,b[r][j]);
			for(int j=0;j<3;j++) A[4].add(r,a[r][j]);
			for(int j=0;j<3;j++) B[4].add(r,b[r][j]);
			if(A[0].ha==B[0].ha&&A[1].ha==B[1].ha&&A[2].ha==B[2].ha
			 &&A[3].ha==B[3].ha&&A[4].ha==B[4].ha){
				continue;
			}
			for(int j=0;j<3;j++) A[0].del(r,a[r][j]);
			for(int j=0;j<3;j++) B[0].del(r,b[r][j]);
			for(int j=0;j<3;j++) A[1].del(r,a[r][j]);
			for(int j=0;j<3;j++) B[1].del(r,b[r][j]);
			for(int j=0;j<3;j++) A[2].del(r,a[r][j]);
			for(int j=0;j<3;j++) B[2].del(r,b[r][j]);
			for(int j=0;j<3;j++) A[3].del(r,a[r][j]);
			for(int j=0;j<3;j++) B[3].del(r,b[r][j]);
			for(int j=0;j<3;j++) A[4].del(r,a[r][j]);
			for(int j=0;j<3;j++) B[4].del(r,b[r][j]);
			r--;
			break;
		}
		for(auto u:vec[l]){
			ans[u.second]=(u.first<=r);
		}
		for(int j=0;j<3;j++) A[0].del(l,a[l][j]);
		for(int j=0;j<3;j++) B[0].del(l,b[l][j]);
		for(int j=0;j<3;j++) A[1].del(l,a[l][j]);
		for(int j=0;j<3;j++) B[1].del(l,b[l][j]);
		for(int j=0;j<3;j++) A[2].del(l,a[l][j]);
		for(int j=0;j<3;j++) B[2].del(l,b[l][j]);
		for(int j=0;j<3;j++) A[3].del(l,a[l][j]);
		for(int j=0;j<3;j++) B[3].del(l,b[l][j]);
		for(int j=0;j<3;j++) A[4].del(l,a[l][j]);
		for(int j=0;j<3;j++) B[4].del(l,b[l][j]);
	}
	for(int i=1;i<=q;i++){
		if(ans[i]) cout<<"Yes\n";
		else cout<<"No\n";
	}
} 

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 7ms
memory: 44596kb

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 20ms
memory: 48560kb

Pretest #10:

score: 5
Accepted
time: 20ms
memory: 46604kb

Pretest #11:

score: 5
Accepted
time: 828ms
memory: 53620kb

Pretest #12:

score: 5
Accepted
time: 832ms
memory: 55744kb

Pretest #13:

score: 5
Accepted
time: 11ms
memory: 46720kb

Pretest #14:

score: 5
Accepted
time: 11ms
memory: 46720kb

Pretest #15:

score: 5
Accepted
time: 117ms
memory: 60348kb

Pretest #16:

score: 5
Accepted
time: 117ms
memory: 58284kb

Pretest #17:

score: 5
Accepted
time: 84ms
memory: 44836kb

Pretest #18:

score: 5
Accepted
time: 76ms
memory: 48972kb

Pretest #19:

score: 5
Accepted
time: 994ms
memory: 66796kb

Pretest #20:

score: 5
Accepted
time: 1013ms
memory: 70932kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

score: 5
Accepted
time: 3ms
memory: 46632kb

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 19ms
memory: 50596kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 831ms
memory: 57260kb

Test #12:

score: 5
Accepted
time: 827ms
memory: 55640kb

Test #13:

score: 5
Accepted
time: 7ms
memory: 44672kb

Test #14:

score: 5
Accepted
time: 9ms
memory: 44688kb

Test #15:

score: 5
Accepted
time: 112ms
memory: 58440kb

Test #16:

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

Test #17:

score: 5
Accepted
time: 76ms
memory: 46904kb

Test #18:

score: 5
Accepted
time: 79ms
memory: 48932kb

Test #19:

score: 5
Accepted
time: 979ms
memory: 68824kb

Test #20:

score: 5
Accepted
time: 1009ms
memory: 70880kb

Extra Test:

score: 0
Extra Test Passed