QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#502458 | #9155. 集合 | nhuang685 | 100 ✓ | 602ms | 63732kb | C++20 | 1.9kb | 2024-08-03 06:27:40 | 2024-08-03 06:27:41 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-08-02 15:07:49
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif
std::mt19937_64
rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::unordered_map<uint64_t, uint64_t> mp;
uint64_t get_hash(uint64_t val) {
if (mp.contains(val)) {
return mp[val];
}
return mp[val] = rng() % (1ULL << 56);
}
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int n, m, q;
std::cin >> n >> m >> q;
std::vector<uint64_t> va(m), vb(m);
std::vector<std::array<int, 3>> a(n), b(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
std::cin >> a[i][j];
--a[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
std::cin >> b[i][j];
--b[i][j];
}
}
uint64_t ta = m * get_hash(0), tb = m * get_hash(0);
auto add_a = [&](int v, int pos) {
ta -= get_hash(va[v]);
va[v] ^= get_hash(pos);
ta += get_hash(va[v]);
};
auto add_b = [&](int v, int pos) {
tb -= get_hash(vb[v]);
vb[v] ^= get_hash(pos);
tb += get_hash(vb[v]);
};
std::vector<int> pl(n);
{
int l = 0;
for (int r = 0; r < n; ++r) {
for (int i = 0; i < 3; ++i) {
add_a(a[r][i], r);
add_b(b[r][i], r);
}
while (l < r && ta != tb) {
for (int i = 0; i < 3; ++i) {
add_a(a[l][i], l);
add_b(b[l][i], l);
}
++l;
}
assert(ta == tb);
pl[r] = l;
}
}
while ((q--) != 0) {
int l, r;
std::cin >> l >> r;
--l;
--r;
if (pl[r] <= l) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3608kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3680kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3568kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3568kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3680kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3564kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 3664kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 3800kb
Pretest #9:
score: 5
Accepted
time: 15ms
memory: 3888kb
Pretest #10:
score: 5
Accepted
time: 19ms
memory: 3692kb
Pretest #11:
score: 5
Accepted
time: 524ms
memory: 60024kb
Pretest #12:
score: 5
Accepted
time: 459ms
memory: 57708kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 4072kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 4372kb
Pretest #15:
score: 5
Accepted
time: 101ms
memory: 4028kb
Pretest #16:
score: 5
Accepted
time: 101ms
memory: 4204kb
Pretest #17:
score: 5
Accepted
time: 26ms
memory: 9168kb
Pretest #18:
score: 5
Accepted
time: 26ms
memory: 9400kb
Pretest #19:
score: 5
Accepted
time: 602ms
memory: 58460kb
Pretest #20:
score: 5
Accepted
time: 534ms
memory: 63032kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3628kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3632kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 3800kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3624kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 3636kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3840kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 3824kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 3604kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 3692kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 3740kb
Test #11:
score: 5
Accepted
time: 444ms
memory: 57912kb
Test #12:
score: 5
Accepted
time: 444ms
memory: 55788kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 3996kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 4080kb
Test #15:
score: 5
Accepted
time: 104ms
memory: 4292kb
Test #16:
score: 5
Accepted
time: 106ms
memory: 4180kb
Test #17:
score: 5
Accepted
time: 15ms
memory: 9244kb
Test #18:
score: 5
Accepted
time: 21ms
memory: 9472kb
Test #19:
score: 5
Accepted
time: 562ms
memory: 57480kb
Test #20:
score: 5
Accepted
time: 551ms
memory: 63732kb
Extra Test:
score: 0
Extra Test Passed