QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#496522#9155. 集合ucup-team1004100 ✓252ms19380kbC++141.7kb2024-07-28 12:45:022024-07-28 12:45:02

Judging History

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

  • [2024-07-28 12:45:02]
  • 评测
  • 测评结果:100
  • 用时:252ms
  • 内存:19380kb
  • [2024-07-28 12:45:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=2e5+10,M=6e5+10;
int n,m,q,a[N][3],b[N][3],ans[N];
void solve(int base,int mod){
	static int pw[N],ta[M],tb[M],oa[M],ob[M];
	for(int i=pw[0]=1;i<=n;i++)pw[i]=1ll*pw[i-1]*base%mod;
	int wa=0,wb=0;
	for(int i=n,j=n;i>=1;i--){
		for(int k=0;k<3;k++){
			ta[a[i][k]]++;
			int &w=oa[a[i][k]];
			wa=(wa+1ll*(mod-w)*w)%mod;
			w=(1ll*w*base+i)%mod;
			wa=(wa+1ll*w*w)%mod;
		}
		for(int k=0;k<3;k++){
			tb[b[i][k]]++;
			int &w=ob[b[i][k]];
			wb=(wb+1ll*(mod-w)*w)%mod;
			w=(1ll*w*base+i)%mod;
			wb=(wb+1ll*w*w)%mod;
		}
		for(;j>i&&wa!=wb;j--){
			for(int k=0;k<3;k++){
				int &w=oa[a[j][k]];
				wa=(wa+1ll*(mod-w)*w)%mod;
				w=(w+1ll*(mod-pw[--ta[a[j][k]]])*j)%mod;
				wa=(wa+1ll*w*w)%mod;
			}
			for(int k=0;k<3;k++){
				int &w=ob[b[j][k]];
				wb=(wb+1ll*(mod-w)*w)%mod;
				w=(w+1ll*(mod-pw[--tb[b[j][k]]])*j)%mod;
				wb=(wb+1ll*w*w)%mod;
			}
		}
		ans[i]=min(ans[i],j);
	}
	for(int i=1;i<=m;i++){
		ta[i]=tb[i]=oa[i]=ob[i]=0;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++)scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++)scanf("%d",&b[i][j]);
	}
	fill(ans+1,ans+1+n,n);
	solve(19260817,1e9+7);
	solve(19260817,1e9+9);
	solve(19260817,998244353);
	for(int l,r;q--;){
		scanf("%d%d",&l,&r);
		puts(ans[l]>=r?"Yes":"No");
	}
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 21ms
memory: 13876kb

Pretest #10:

score: 5
Accepted
time: 18ms
memory: 14064kb

Pretest #11:

score: 5
Accepted
time: 144ms
memory: 14212kb

Pretest #12:

score: 5
Accepted
time: 140ms
memory: 15044kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 100ms
memory: 11868kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 250ms
memory: 17216kb

Pretest #20:

score: 5
Accepted
time: 250ms
memory: 19304kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 21ms
memory: 12020kb

Test #10:

score: 5
Accepted
time: 18ms
memory: 15972kb

Test #11:

score: 5
Accepted
time: 145ms
memory: 16008kb

Test #12:

score: 5
Accepted
time: 129ms
memory: 14340kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 95ms
memory: 13880kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

score: 5
Accepted
time: 252ms
memory: 19380kb

Extra Test:

score: 0
Extra Test Passed