QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605775 | #9155. 集合 | XuYueming | 100 ✓ | 507ms | 64876kb | C++23 | 2.1kb | 2024-10-02 19:32:48 | 2024-10-02 19:32:49 |
Judging History
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