QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#503630 | #9155. 集合 | zlxFTH | 100 ✓ | 528ms | 82712kb | C++17 | 1.7kb | 2024-08-03 21:22:32 | 2024-08-03 21:22:33 |
Judging History
answer
#include <bits/stdc++.h>
using u64 = unsigned long long;
std::mt19937_64 rnd(std::random_device{}());
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::array<int, 3>> a(n), b(n);
for (int i = 0; i < n; i++) {
for (auto &v : a[i]) {
std::cin >> v;
v--;
}
}
for (int i = 0; i < n; i++) {
for (auto &v : b[i]) {
std::cin >> v;
v--;
}
}
std::vector<int> ql(q), qr(q);
std::vector c(n, std::vector<int>());
for (int i = 0; i < q; i++) {
std::cin >> ql[i] >> qr[i];
ql[i]--, qr[i]--;
c[qr[i]].emplace_back(i);
}
int bad = 0;
std::unordered_map<u64, int> f;
auto modify = [&](u64 key, int val) {
if (f[key] != 0) {
bad--;
}
f[key] += val;
if (f[key] != 0) {
bad++;
}
};
std::vector<u64> ha(m), hb(m), d(n);
auto add = [&](int p) {
for (auto v : a[p]) {
modify(ha[v], -1);
ha[v] ^= d[p];
modify(ha[v], 1);
}
for (auto v : b[p]) {
modify(hb[v], 1);
hb[v] ^= d[p];
modify(hb[v], -1);
}
};
std::vector<int> ans(q);
int l = 0;
for (int r = 0; r < n; r++) {
d[r] = rnd();
add(r);
while (l <= r && bad) {
add(l++);
}
for (auto i : c[r]) {
if (ql[i] >= l) {
ans[i] = 1;
}
}
}
for (int i = 0; i < q; i++) {
std::cout << (ans[i] ? "Yes" : "No") << "\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 3640kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3632kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3616kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3840kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3612kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3612kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 3680kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 3812kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 6740kb
Pretest #10:
score: 5
Accepted
time: 24ms
memory: 6724kb
Pretest #11:
score: 5
Accepted
time: 386ms
memory: 64748kb
Pretest #12:
score: 5
Accepted
time: 330ms
memory: 62300kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 4092kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 4356kb
Pretest #15:
score: 5
Accepted
time: 115ms
memory: 21544kb
Pretest #16:
score: 5
Accepted
time: 99ms
memory: 21308kb
Pretest #17:
score: 5
Accepted
time: 19ms
memory: 9028kb
Pretest #18:
score: 5
Accepted
time: 23ms
memory: 10040kb
Pretest #19:
score: 5
Accepted
time: 521ms
memory: 77744kb
Pretest #20:
score: 5
Accepted
time: 528ms
memory: 82700kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3760kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3552kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3828kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3604kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 3796kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3560kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 3672kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 3572kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 6800kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 6792kb
Test #11:
score: 5
Accepted
time: 336ms
memory: 62608kb
Test #12:
score: 5
Accepted
time: 334ms
memory: 60580kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 4072kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 4132kb
Test #15:
score: 5
Accepted
time: 120ms
memory: 21424kb
Test #16:
score: 5
Accepted
time: 122ms
memory: 21308kb
Test #17:
score: 5
Accepted
time: 21ms
memory: 9080kb
Test #18:
score: 5
Accepted
time: 18ms
memory: 9968kb
Test #19:
score: 5
Accepted
time: 517ms
memory: 76676kb
Test #20:
score: 5
Accepted
time: 505ms
memory: 82712kb
Extra Test:
score: 0
Extra Test Passed