QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502452#9155. 集合alexz1205100 ✓199ms20220kbC++141.4kb2024-08-03 06:14:162024-08-03 06:14:23

Judging History

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

  • [2024-08-03 06:14:23]
  • 评测
  • 测评结果:100
  • 用时:199ms
  • 内存:20220kb
  • [2024-08-03 06:14:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long int lint;

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

mt19937_64 ran;

lint getRand(){
	return (lint)ran();
}

lint randHash[N];
lint ap1[M+1];
lint ap2[M+1];
lint h1, h2;

int arr1[N][3];
int arr2[N][3];

int ans[N];

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int x = 0; x < n; x ++){
		randHash[x] = getRand();
	}
	for (int x = 0; x < n; x ++){
		for (int i = 0; i < 3; i ++){
			scanf("%d", &arr1[x][i]);
		}
	}
	for (int x = 0; x < n; x ++){
		for (int i = 0; i < 3; i ++){
			scanf("%d", &arr2[x][i]);
		}
	}
	int i = 0, j = -1;
	while (i < n){
		//printf("%d %d %d %d\n", i, j, h1, h2);
		if (h1 == h2){
			if (j == n-1){
				ans[i] = j;
				i ++;
				continue;
			}
			j ++;
			for (int x = 0; x < 3; x ++){
				int v1 = arr1[j][x], v2 = arr2[j][x];
				h1 -= ap1[v1];
				ap1[v1] ^= randHash[j];
				h1 += ap1[v1];

				h2 -= ap2[v2];
				ap2[v2] ^= randHash[j];
				h2 += ap2[v2];
			}
		}else {
			ans[i] = j-1;
			for (int x = 0; x < 3; x ++){
				int v1 = arr1[i][x], v2 = arr2[i][x];
				h1 -= ap1[v1];
				ap1[v1] ^= randHash[i];
				h1 += ap1[v1];

				h2 -= ap2[v2];
				ap2[v2] ^= randHash[i];
				h2 += ap2[v2];
			}
			i ++;
		}
	}
	for (int x = 0; x < q; x ++){
		int l, r;
		scanf("%d %d", &l, &r);
		l --, r --;
		if (r <= ans[l]){
			printf("Yes\n");
		}else {
			printf("No\n");
		}
	}
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 19ms
memory: 7908kb

Pretest #11:

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

Pretest #12:

score: 5
Accepted
time: 77ms
memory: 14064kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 117ms
memory: 7932kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 195ms
memory: 14084kb

Pretest #20:

score: 5
Accepted
time: 199ms
memory: 20220kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 79ms
memory: 12080kb

Test #12:

score: 5
Accepted
time: 69ms
memory: 11964kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 114ms
memory: 8044kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 183ms
memory: 14168kb

Test #20:

score: 5
Accepted
time: 186ms
memory: 20220kb

Extra Test:

score: 0
Extra Test Passed