QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605775#9155. 集合XuYueming100 ✓507ms64876kbC++232.1kb2024-10-02 19:32:482024-10-02 19:32:49

Judging History

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

  • [2024-10-02 19:32:49]
  • 评测
  • 测评结果:100
  • 用时:507ms
  • 内存:64876kb
  • [2024-10-02 19:32:48]
  • 提交

answer

// #pragma GCC optimize("Ofast", "inline", "fast-math")

#include <cstring>
#include <iostream>
#include <unordered_map>
#include <cassert>
#include <cstdio>
#include <limits>
#include <random>
#include <ctime>
using namespace std;

using uint = unsigned;
using ull = unsigned long long;

mt19937 rnd(101108);

const int N = 1000010;

int n, m, q;
unordered_map<ull, int> cnt;

inline ull O(ull x) {
	x ^= 45151, x ^= x >> 2, x ^= x << 4;
	return x * x + (651 ^ x) + x * x * 13132;
}

inline ull K(ull x) {
	x *= 51564, x ^= 31561, x ^= O(x) << 3;
	return (x ^ 5614561) + x * x * O(x) * 131 + O(x * 465415);
}

inline ull G(ull x) {
	x ^= x >> 2, x ^= x << 4, x *= 515654;
	return x * x * x * 156 + (x ^ 5645) * 651 + K(K(x * x)) * K(x ^ 1361) + K(x >> 4 << 14 | 1151);
}

inline ull F(ull x) {
	x *= 1315615ll, x ^= 545451356, x ^= x << 2;
	return G(x * 321) * 315615 + G(G(G(x * x + 6541))) * 56141;
}

ull w[N], a[N], b[N];
int va[N][3], vb[N][3], R[N], ans;

inline void add(ull x) { cnt[x]++ && --ans, cnt[x] && ++ans; }
inline void del(ull x) { cnt[x]-- && --ans, cnt[x] && ++ans; }
inline void upd(int p, int f) {
	del(a[va[p][0]]), del(a[va[p][1]]), del(a[va[p][2]]);
	if (f == 1) a[va[p][0]] += w[p], a[va[p][1]] += w[p], a[va[p][2]] += w[p];
	else a[va[p][0]] -= w[p], a[va[p][1]] -= w[p], a[va[p][2]] -= w[p];
	add(a[va[p][0]]), add(a[va[p][1]]), add(a[va[p][2]]);
	
	add(b[vb[p][0]]), add(b[vb[p][1]]), add(b[vb[p][2]]);
	if (f == 1) b[vb[p][0]] += w[p], b[vb[p][1]] += w[p], b[vb[p][2]] += w[p];
	else b[vb[p][0]] -= w[p], b[vb[p][1]] -= w[p], b[vb[p][2]] -= w[p];
	del(b[vb[p][0]]), del(b[vb[p][1]]), del(b[vb[p][2]]);
}

signed main() {
    scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; ++i) scanf("%d%d%d", &va[i][0], &va[i][1], &va[i][2]);
	for (int i = 1; i <= n; ++i) scanf("%d%d%d", &vb[i][0], &vb[i][1], &vb[i][2]);
	for (int i = 1; i <= n; ++i) w[i] = F(1ull * i * n * m * q);
	for (int i = 1, j = 0; i <= n; R[i] = j, upd(i++, -1)) while (j <= n && !ans) upd(++j, 1);
	for (int l, r; q--; scanf("%d%d", &l, &r), puts(R[l] > r ? "Yes" : "No"));
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 393ms
memory: 62836kb

Pretest #12:

score: 5
Accepted
time: 383ms
memory: 59128kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 106ms
memory: 10208kb

Pretest #16:

score: 5
Accepted
time: 95ms
memory: 10568kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 27ms
memory: 15084kb

Pretest #19:

score: 5
Accepted
time: 490ms
memory: 57988kb

Pretest #20:

score: 5
Accepted
time: 497ms
memory: 64876kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 393ms
memory: 61112kb

Test #12:

score: 5
Accepted
time: 401ms
memory: 57364kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 507ms
memory: 60292kb

Test #20:

score: 5
Accepted
time: 476ms
memory: 62824kb

Extra Test:

score: 0
Extra Test Passed