QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488478#9155. 集合JohnAlfnov#100 ✓670ms161184kbC++141.7kb2024-07-24 08:06:272024-07-24 08:06:27

Judging History

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

  • [2024-07-24 08:06:27]
  • 评测
  • 测评结果:100
  • 用时:670ms
  • 内存:161184kb
  • [2024-07-24 08:06:27]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define ull unsigned long long
ull seed=19730619;
ull ran(){
	seed^=seed<<13;
	seed^=seed>>7;
	seed^=seed<<17;
	return seed;
}
ull rd[200005];
__gnu_pbds::cc_hash_table<ull,int>m1,m2;
int rt[200005];
int a[200005][3],b[200005][3];
ull ha[600005],hb[600005];
int cj=0;
void add(int x){
	for(int i=0;i<3;++i){
		int z=a[x][i];
		int g1=m1[ha[z]],g2=m2[ha[z]];
		--m1[ha[z]];cj+=abs(g1-1-g2)-abs(g1-g2);
		ha[z]^=rd[x];
		int h1=m1[ha[z]],h2=m2[ha[z]];
		++m1[ha[z]];cj+=abs(h1+1-h2)-abs(h1-h2);
	}
	for(int i=0;i<3;++i){
		int z=b[x][i];
		int g1=m2[hb[z]],g2=m1[hb[z]];
		--m2[hb[z]];cj+=abs(g1-1-g2)-abs(g1-g2);
		hb[z]^=rd[x];
		int h1=m2[hb[z]],h2=m1[hb[z]];
		++m2[hb[z]];cj+=abs(h1+1-h2)-abs(h1-h2);
	}
}
void del(int x){
	for(int i=0;i<3;++i){
		int z=a[x][i];
		int g1=m1[ha[z]],g2=m2[ha[z]];
		--m1[ha[z]];cj+=abs(g1-1-g2)-abs(g1-g2);
		ha[z]^=rd[x];
		int h1=m1[ha[z]],h2=m2[ha[z]];
		++m1[ha[z]];cj+=abs(h1+1-h2)-abs(h1-h2);
	}
	for(int i=0;i<3;++i){
		int z=b[x][i];
		int g1=m2[hb[z]],g2=m1[hb[z]];
		--m2[hb[z]];cj+=abs(g1-1-g2)-abs(g1-g2);
		hb[z]^=rd[x];
		int h1=m2[hb[z]],h2=m1[hb[z]];
		++m2[hb[z]];cj+=abs(h1+1-h2)-abs(h1-h2);
	}
}
int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)rd[i]=ran();
	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]);
	m1[0]=m2[0]=n;
	int r=1;
	add(r);
	for(int l=1;l<=n;++l){
		while(r<=n&&cj==0){
			++r;
			if(r<=n)add(r);
		}
		rt[l]=r-1;
		del(l);
	}
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		puts(rt[l]>=r?"Yes":"No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 17ms
memory: 12236kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 660ms
memory: 161184kb

Pretest #12:

score: 5
Accepted
time: 548ms
memory: 115008kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 109ms
memory: 10728kb

Pretest #16:

score: 5
Accepted
time: 105ms
memory: 10628kb

Pretest #17:

score: 5
Accepted
time: 31ms
memory: 21520kb

Pretest #18:

score: 5
Accepted
time: 30ms
memory: 23052kb

Pretest #19:

score: 5
Accepted
time: 670ms
memory: 116472kb

Pretest #20:

score: 5
Accepted
time: 626ms
memory: 115712kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 17ms
memory: 10000kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 575ms
memory: 115972kb

Test #12:

score: 5
Accepted
time: 556ms
memory: 111132kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 111ms
memory: 10664kb

Test #17:

score: 5
Accepted
time: 28ms
memory: 23392kb

Test #18:

score: 5
Accepted
time: 29ms
memory: 20728kb

Test #19:

score: 5
Accepted
time: 642ms
memory: 114108kb

Test #20:

score: 5
Accepted
time: 646ms
memory: 116764kb

Extra Test:

score: 0
Extra Test Passed