QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490062#9155. 集合wxqwq100 ✓112ms34140kbC++142.1kb2024-07-25 10:56:412024-07-25 10:56:41

Judging History

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

  • [2024-07-25 10:56:41]
  • 评测
  • 测评结果:100
  • 用时:112ms
  • 内存:34140kb
  • [2024-07-25 10:56:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') f=1;ch=getchar();}
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}

#define x first
#define y second
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)

typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ull;
const int N=2e5+10,M=6e5+10;
const ull P=998244853;

int n,m,q;
ull pa[N*3],pb[N*3],w[N];
int a[N][3],b[N][3];
int pre[N*3],lst[M],prb[N*3],lsb[M];
int psa[M],psb[M];
int R[N];

ull myrd() {
	ull x=rand()*1llu*rand();
	x^=x<<23,x|=x<<17,x^=x>>13;
	return x;
}
int main()
{
	n=read(),m=read(),q=read();//,srand(time(NULL));
	for(int i=1;i<=n;i++) w[i]=myrd();
	// rep(i,1,n) cout<<w[i]<<endl;
	for(int i=1,o=1,x;i<=n;i++,o+=3) rep(j,0,2) {
		x=read(),pre[o+j]=lst[x],a[i][j]=x;
		pa[o+j]=pa[lst[x]]^w[i],lst[x]=o+j;
	} for(int i=1,o=1,x;i<=n;i++,o+=3) rep(j,0,2) {
		x=read(),prb[o+j]=lsb[x],b[i][j]=x;
		pb[o+j]=pb[lsb[x]]^w[i],lsb[x]=o+j;
	}
	rep(i,1,m) psa[i]=lst[i],psb[i]=lsb[i];
	
	R[n+1]=n;
	// cout<<(pa[4]^pa[10])<<endl;
	for(int i=n,o=n*3-2;i>=1;i--,o-=3) {
		rep(j,0,2) while(psa[a[i][j]]>=o) psa[a[i][j]]=pre[psa[a[i][j]]];
		rep(j,0,2) while(psb[b[i][j]]>=o) psb[b[i][j]]=prb[psb[b[i][j]]];
		int r=R[i+1];
		for(;r>i;r--) {
			rep(j,0,2) while(lst[a[i][j]]>r*3) lst[a[i][j]]=pre[lst[a[i][j]]];
			rep(j,0,2) while(lsb[b[i][j]]>r*3) lsb[b[i][j]]=prb[lsb[b[i][j]]];
			ull sa[3]={0,0,0},sb[3]={0,0,0};
			rep(j,0,2) {
				sa[j]=pa[lst[a[i][j]]]^pa[psa[a[i][j]]];
				sb[j]=pb[lsb[b[i][j]]]^pb[psb[b[i][j]]];
			}
			// rep(j,0,2) cout<<sa[j]<<' '<<sb[j]<<' '<<lst[a[i][j]]<<' '<<psa[a[i][j]]<<endl;
			sort(sa,sa+3),sort(sb,sb+3); bool ok=1;
			rep(j,0,2) ok&=(sa[j]==sb[j]);
			if(ok) break;
		}
		// rep(j,1,m) cout<<lst[j]<<' '; puts("");
		R[i]=r;
		// cout<<i<<' '<<R[i]<<' '<<r<<endl;
	}
	
	int l,r;
	while(q--) {
		l=read(),r=read();
		if(R[l]>=r) puts("Yes");
		else puts("No");
	}
	
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 10ms
memory: 15880kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 37ms
memory: 31500kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 48ms
memory: 15916kb

Pretest #16:

score: 5
Accepted
time: 49ms
memory: 18036kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 8ms
memory: 19388kb

Pretest #19:

score: 5
Accepted
time: 106ms
memory: 27552kb

Pretest #20:

score: 5
Accepted
time: 99ms
memory: 34140kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 49ms
memory: 31592kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 47ms
memory: 16044kb

Test #16:

score: 5
Accepted
time: 42ms
memory: 16132kb

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Extra Test:

score: 0
Extra Test Passed