QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492282#9155. 集合C1942huangjiaxu100 ✓57ms28224kbC++141.1kb2024-07-26 11:07:372024-07-26 11:07:38

Judging History

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

  • [2024-07-26 11:07:38]
  • 评测
  • 测评结果:100
  • 用时:57ms
  • 内存:28224kb
  • [2024-07-26 11:07:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
mt19937_64 rnd(0x66ccff);
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
	char c=getchar();
	for(;c<48||c>57;c=getchar());
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
int n,m,q,a[N][3],b[N][3],p[N];
ull val(ull x){
	x^=x<<13;
	x^=x>>7;
	x^=x<<17;
	return x+0x66ccff;
}
ull w[N],va,vb,wa[N*3],wb[N*3];
void add(int x,int o){
	for(int j=0,v;j<3;++j){
		v=a[x][j];
		va-=val(wa[v]);
		wa[v]+=w[x]*o;
		va+=val(wa[v]);
		v=b[x][j];
		vb-=val(wb[v]);
		wb[v]+=w[x]*o;
		vb+=val(wb[v]);
	}
}
int main(){
	read(n),read(m),read(q);
	for(int i=1;i<=n;++i)for(int j=0;j<3;++j)read(a[i][j]);
	for(int i=1;i<=n;++i)for(int j=0;j<3;++j)read(b[i][j]);
	for(int i=1;i<=n;++i)w[i]=rnd();
	for(int i=n,j=n;i;--i){
		add(i,1);
		while(va!=vb)add(j--,-1);
		p[i]=j;
	}
	for(int i=1,l,r;i<=q;++i){
		read(l),read(r);
		puts(p[l]>=r?"Yes":"No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

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

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 24ms
memory: 19488kb

Pretest #16:

score: 5
Accepted
time: 33ms
memory: 20088kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

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

Pretest #20:

score: 5
Accepted
time: 57ms
memory: 28224kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 14ms
memory: 18028kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 24ms
memory: 18920kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 54ms
memory: 19828kb

Test #20:

score: 5
Accepted
time: 52ms
memory: 28160kb

Extra Test:

score: 0
Extra Test Passed