QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504287#9155. 集合Bitter100 ✓404ms30072kbC++143.3kb2024-08-04 11:31:302024-08-04 11:31:32

Judging History

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

  • [2024-08-04 11:31:32]
  • 评测
  • 测评结果:100
  • 用时:404ms
  • 内存:30072kb
  • [2024-08-04 11:31:30]
  • 提交

answer

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb emplace_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			w = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}
const int base1 = 3;
const int base2 = 7;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 7;
const int N = 6e5 + 10;
int h1[N], h2[N], pw1[N], pw2[N];
int H1[N], H2[N];
inline int Add(int x, int y, int op = 0) {
	if(!op) return (x + y) % mod1;
	return (x + y) % mod2;
}
inline int Mul(int x, int y, int op = 0) {
	if(!op) return 1ll * x * y % mod1;
	return 1ll * x * y % mod2;
}
int n, a[N][3], m, q, b[N][3];
int A1, B1, A2, B2;
unsigned long long a1, b1, a2, b2;
int rig[N];
inline int insert(int p) {
	if(p > n) return 0;
	for(int i = 0; i < 3; ++i) {
		int u = a[p][i];
		A1 ^= h1[u];
		A2 ^= h2[u];
		a1 -= h1[u];
		a2 -= h2[u];
		h1[u] = Add(h1[u], pw1[p]);
		h2[u] = Add(h2[u], pw2[p], 1);
		A1 ^= h1[u];
		A2 ^= h2[u];
		a2 += h2[u];
		a1 += h1[u];
	}
	for(int i = 0; i < 3; ++i) {
		int u = b[p][i];
		b1 -= H1[u];
		b2 -= H2[u];
		B1 ^= H1[u];
		B2 ^= H2[u];
		H1[u] = Add(H1[u], pw1[p]);
		H2[u] = Add(H2[u], pw2[p], 1);
		B1 ^= H1[u];
		B2 ^= H2[u];
		b1 += H1[u];
		b2 += H2[u];
	}
	return A1 == B1 && A2 == B2 && a1 == b1 && a2 == b2;
}
inline int del(int p) {
	if(p > n) return 0;
	for(int i = 0; i < 3; ++i) {
		int u = a[p][i];
		A1 ^= h1[u];
		A2 ^= h2[u];
		a1 -= h1[u];
		a2 -= h2[u];
		h1[u] = Add(h1[u], mod1 - pw1[p]);
		h2[u] = Add(h2[u], mod2 - pw2[p], 1);
		A1 ^= h1[u];
		A2 ^= h2[u];
		a2 += h2[u];
		a1 += h1[u];
	}
	for(int i = 0; i < 3; ++i) {
		int u = b[p][i];
		B1 ^= H1[u];
		B2 ^= H2[u];
		b1 -= H1[u];
		b2 -= H2[u];
		H1[u] = Add(H1[u], mod1 - pw1[p]);
		H2[u] = Add(H2[u], mod2 - pw2[p], 1);
		B1 ^= H1[u];
		B2 ^= H2[u];
		b1 += H1[u];
		b2 += H2[u];
	}
	return A1 == B1 && A2 == B2 && a1 == b1 && a2 == b2;
}
mt19937 rnd(time(0));
unsigned long long msk;
inline int rd(int x) {
	x = x * 1ull;
	x ^= msk;
	x ^= (x << 7);
	x ^= (x >> 11);
	x ^= (x << 13);
	if(x < 0) x = -x;
	x %= mod1;
	return x;
}
int main() {
	n = read(), m = read(), q = read();
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < 3; ++j) a[i][j] = read();
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < 3; ++j) b[i][j] = read();
	}
	int test = 10;
	while(test--) {
		msk = rnd();
		
		pw1[0] = pw2[0] = 1;
		for(int i = 1; i <= 600000; ++i) {
			pw1[i] = Mul(pw1[i - 1], base1);
			pw2[i] = Mul(pw2[i - 1], base2, 1);
		}
		for(int i = 1; i <= 600000; ++i) {
			pw1[i] = Mul(pw1[i], i);
			pw2[i] = Mul(pw2[i], i, 1);
			pw1[i] = Add(pw1[i], rd(i));
			pw2[i] = Add(pw2[i], rd(i), 1);
		}
		int r = 1;
		a1 = b1 = a2 = b2 = A1 = B1 = A2 = B2 = 0;
		for(int i = 1; i <= n; ++i) {
			h1[i] = h2[i] = H1[i] = H2[i] = 0;
		}
		for(int l = 1; l <= n; ++l) {
			while(r <= n && insert(r)) r = r + 1;
			if(!rig[l]) rig[l] = r - 1;
			else {
				rig[l] = min(rig[l], r - 1);
			}
			if(r <= n) del(r);
			del(l);
		}
	}

	while(q--) {
		int ql = read(), qr = read();
		if(qr <= rig[ql]) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

詳細信息


Pretests

Pretest #1:

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

Pretest #2:

score: 5
Accepted
time: 62ms
memory: 22240kb

Pretest #3:

score: 5
Accepted
time: 61ms
memory: 20144kb

Pretest #4:

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

Pretest #5:

score: 5
Accepted
time: 58ms
memory: 22184kb

Pretest #6:

score: 5
Accepted
time: 65ms
memory: 22100kb

Pretest #7:

score: 5
Accepted
time: 62ms
memory: 20132kb

Pretest #8:

score: 5
Accepted
time: 61ms
memory: 20016kb

Pretest #9:

score: 5
Accepted
time: 71ms
memory: 22192kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 309ms
memory: 26944kb

Pretest #12:

score: 5
Accepted
time: 312ms
memory: 26992kb

Pretest #13:

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

Pretest #14:

score: 5
Accepted
time: 68ms
memory: 20192kb

Pretest #15:

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

Pretest #16:

score: 5
Accepted
time: 113ms
memory: 22068kb

Pretest #17:

score: 5
Accepted
time: 90ms
memory: 22120kb

Pretest #18:

score: 5
Accepted
time: 86ms
memory: 20080kb

Pretest #19:

score: 5
Accepted
time: 373ms
memory: 26976kb

Pretest #20:

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

Final Tests

Test #1:

score: 5
Accepted
time: 66ms
memory: 22152kb

Test #2:

score: 5
Accepted
time: 66ms
memory: 20060kb

Test #3:

score: 5
Accepted
time: 61ms
memory: 20016kb

Test #4:

score: 5
Accepted
time: 58ms
memory: 20056kb

Test #5:

score: 5
Accepted
time: 58ms
memory: 20132kb

Test #6:

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

Test #7:

score: 5
Accepted
time: 62ms
memory: 20056kb

Test #8:

score: 5
Accepted
time: 58ms
memory: 22236kb

Test #9:

score: 5
Accepted
time: 76ms
memory: 20192kb

Test #10:

score: 5
Accepted
time: 76ms
memory: 19992kb

Test #11:

score: 5
Accepted
time: 313ms
memory: 26976kb

Test #12:

score: 5
Accepted
time: 313ms
memory: 29160kb

Test #13:

score: 5
Accepted
time: 64ms
memory: 20140kb

Test #14:

score: 5
Accepted
time: 59ms
memory: 20200kb

Test #15:

score: 5
Accepted
time: 115ms
memory: 22188kb

Test #16:

score: 5
Accepted
time: 124ms
memory: 20140kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 87ms
memory: 24316kb

Test #19:

score: 5
Accepted
time: 366ms
memory: 29028kb

Test #20:

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

Extra Test:

score: 0
Extra Test Passed