QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491760#9155. 集合Snail2956100 ✓404ms62364kbC++141.0kb2024-07-25 21:52:432024-07-25 21:52:44

Judging History

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

  • [2024-07-25 21:52:44]
  • 评测
  • 测评结果:100
  • 用时:404ms
  • 内存:62364kb
  • [2024-07-25 21:52:43]
  • 提交

answer

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<random>
#include<unordered_map>

using namespace std;

const int N=2e5+10,M=6e5+10;

int n,m,q;
int a[N][4],b[N][4];
int l,r,p[N],tot;
unsigned long long h[M],ha[M],hb[M];
unordered_map<unsigned long long,int> cnt;

mt19937_64 rnd(time(0));

void add(unsigned __int128 x){cnt[x]++&&tot--,cnt[x]&&tot++;}
void del(unsigned __int128 x){cnt[x]--&&tot--,cnt[x]&&tot++;}

void upd(int i,int t){
	for(int k=1;k<=3;k++) del(ha[a[i][k]]),ha[a[i][k]]+=t*h[i],add(ha[a[i][k]]);
	for(int k=1;k<=3;k++) add(hb[b[i][k]]),hb[b[i][k]]+=t*h[i],del(hb[b[i][k]]);
}

void init(){
	for(int i=1;i<=n;i++) h[i]=rnd();
	for(int i=1,j=0;i<=n;i++){
		while(j<=n&&!tot) upd(++j,1);
		p[i]=j-1,upd(i,-1);
	}
}

int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%d %d %d",&a[i][1],&a[i][2],&a[i][3]);
	for(int i=1;i<=n;i++) scanf("%d %d %d",&b[i][1],&b[i][2],&b[i][3]);
	init();
	while(q--){
		scanf("%d %d",&l,&r);
		printf(p[l]>=r?"Yes\n":"No\n");
	}
	return 0;
}

詳細信息


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 16ms
memory: 10056kb

Pretest #11:

score: 5
Accepted
time: 281ms
memory: 59592kb

Pretest #12:

score: 5
Accepted
time: 280ms
memory: 57160kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 119ms
memory: 10268kb

Pretest #16:

score: 5
Accepted
time: 118ms
memory: 10356kb

Pretest #17:

score: 5
Accepted
time: 20ms
memory: 14184kb

Pretest #18:

score: 5
Accepted
time: 20ms
memory: 17344kb

Pretest #19:

score: 5
Accepted
time: 402ms
memory: 58316kb

Pretest #20:

score: 5
Accepted
time: 403ms
memory: 61360kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 23ms
memory: 9964kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 292ms
memory: 57488kb

Test #12:

score: 5
Accepted
time: 277ms
memory: 53972kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 103ms
memory: 10268kb

Test #16:

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

Test #17:

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

Test #18:

score: 5
Accepted
time: 12ms
memory: 17072kb

Test #19:

score: 5
Accepted
time: 389ms
memory: 56788kb

Test #20:

score: 5
Accepted
time: 404ms
memory: 62364kb

Extra Test:

score: 0
Extra Test Passed