QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#493259#9155. 集合Sham_Devour100 ✓201ms18588kbC++141.5kb2024-07-26 23:04:312024-07-26 23:04:31

Judging History

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

  • [2024-07-26 23:04:31]
  • 评测
  • 测评结果:100
  • 用时:201ms
  • 内存:18588kb
  • [2024-07-26 23:04:31]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <random>
#include <ctime>
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 5, M = 6e5 + 5;
mt19937_64 rng(time(0));

int n, m, q, pos[N];
ull msk = rng(), hsa, hsb, vala[M], valb[M];

ull shift(ull x) {
	x ^= msk;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	x ^= msk;
	return x;
}

struct node {
	int x, y, z;
} a[N], b[N];

void upda(int x, int p, int op) {
	hsa -= shift(vala[x]);
	vala[x] += shift(p) * op;
	hsa += shift(vala[x]);
}
void updb(int x, int p, int op) {
	hsb -= shift(valb[x]);
	valb[x] += shift(p) * op;
	hsb += shift(valb[x]);
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= n; i++) scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
	for (int i = 1; i <= n; i++) scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z);
	for (int l = 1, r = 0; l <= n; l++) {
		while (r < n) {
			r++;
			upda(a[r].x, r, 1), upda(a[r].y, r, 1), upda(a[r].z, r, 1);
			updb(b[r].x, r, 1), updb(b[r].y, r, 1), updb(b[r].z, r, 1);
			if (hsa != hsb) {
				upda(a[r].x, r, -1), upda(a[r].y, r, -1), upda(a[r].z, r, -1);
				updb(b[r].x, r, -1), updb(b[r].y, r, -1), updb(b[r].z, r, -1);
				r--;
				break;
			}
		}
		pos[l] = r;
		if (l <= r) {
			upda(a[l].x, l, -1), upda(a[l].y, l, -1), upda(a[l].z, l, -1);
			updb(b[l].x, l, -1), updb(b[l].y, l, -1), updb(b[l].z, l, -1);
		}
	}
	while (q--) {
		int l, r;
		scanf("%d %d", &l, &r);
		puts(pos[l] >= r ? "Yes" : "No");
	}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 72ms
memory: 9972kb

Pretest #12:

score: 5
Accepted
time: 82ms
memory: 9288kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 104ms
memory: 6076kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 11212kb

Pretest #19:

score: 5
Accepted
time: 175ms
memory: 9648kb

Pretest #20:

score: 5
Accepted
time: 201ms
memory: 18588kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 84ms
memory: 9996kb

Test #12:

score: 5
Accepted
time: 82ms
memory: 9840kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 185ms
memory: 12448kb

Test #20:

score: 5
Accepted
time: 197ms
memory: 18584kb

Extra Test:

score: 0
Extra Test Passed