QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489126#9155. 集合pengyule100 ✓858ms113832kbC++141.8kb2024-07-24 18:19:522024-07-24 18:19:54

Judging History

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

  • [2024-07-24 18:19:54]
  • 评测
  • 测评结果:100
  • 用时:858ms
  • 内存:113832kb
  • [2024-07-24 18:19:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int buflen=1<<21;
int x,f;
char ch,buf[buflen],*p1=buf,*p2=buf;
inline char gc(){return p1==p2&&(p2=buf+fread(p1=buf,1,buflen,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
	x=0,f=1,ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return f?x:-x;
}
}
using IO::read;
const int N=1e6+5;
const ll base=37,mod=1e9+7;
int n,m,q,a[N][4],b[N][4],lim[N];
ll A[N],B[N],mi[N];
unordered_map<ll,int>S,T;
inline void add(ll &x,ll y){(x+=y)>=mod&&(x-=mod);}
bool Add(int p){
	vector<ll>vec;
	for(int j=1;j<=3;j++){
		S[A[a[p][j]]]--;
		vec.emplace_back(A[a[p][j]]);
		add(A[a[p][j]],mi[p]);
		vec.emplace_back(A[a[p][j]]);
		S[A[a[p][j]]]++;
		vec.emplace_back(B[b[p][j]]);
		T[B[b[p][j]]]--;
		add(B[b[p][j]],mi[p]);
		vec.emplace_back(B[b[p][j]]);
		T[B[b[p][j]]]++;
	}
	for(ll e:vec){
		if(S[e]!=T[e]){
			for(int j=3;j>=1;j--){
				S[A[a[p][j]]]--;
				add(A[a[p][j]],mod-mi[p]);
				S[A[a[p][j]]]++;
				T[B[b[p][j]]]--;
				add(B[b[p][j]],mod-mi[p]);
				T[B[b[p][j]]]++;
			}
			return 0;
		}
	}
	return 1;
}
void Del(int p){
	for(int j=1;j<=3;j++){
		S[A[a[p][j]]]--;
		add(A[a[p][j]],mod-mi[p]);
		S[A[a[p][j]]]++;
		T[B[b[p][j]]]--;
		add(B[b[p][j]],mod-mi[p]);
		T[B[b[p][j]]]++;
	}
}
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)a[i][j]=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)b[i][j]=read();
	mi[0]=1;
	for(int i=1;i<=n;i++)mi[i]=mi[i-1]*base%mod;
	for(int i=1,j=0;i<=n;i++){
		j=max(j,i-1);
		while(j<n&&Add(j+1))j++;
		lim[i]=j;
		Del(i);
	}
	for(int i=1,l,r;i<=q;i++){
		l=read(),r=read();
		puts(r<=lim[l]?"Yes":"No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 858ms
memory: 113832kb

Pretest #12:

score: 5
Accepted
time: 826ms
memory: 107496kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 43ms
memory: 12664kb

Pretest #16:

score: 5
Accepted
time: 43ms
memory: 14356kb

Pretest #17:

score: 5
Accepted
time: 38ms
memory: 23076kb

Pretest #18:

score: 5
Accepted
time: 27ms
memory: 21000kb

Pretest #19:

score: 5
Accepted
time: 811ms
memory: 108680kb

Pretest #20:

score: 5
Accepted
time: 763ms
memory: 110580kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 797ms
memory: 112880kb

Test #12:

score: 5
Accepted
time: 735ms
memory: 105224kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 38ms
memory: 13448kb

Test #16:

score: 5
Accepted
time: 40ms
memory: 13768kb

Test #17:

score: 5
Accepted
time: 41ms
memory: 21660kb

Test #18:

score: 5
Accepted
time: 36ms
memory: 21256kb

Test #19:

score: 5
Accepted
time: 767ms
memory: 108284kb

Test #20:

score: 5
Accepted
time: 735ms
memory: 109048kb

Extra Test:

score: 0
Extra Test Passed