QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505032 | #9155. 集合 | JCY_ | 100 ✓ | 283ms | 19956kb | C++23 | 1.5kb | 2024-08-04 18:31:53 | 2024-08-04 18:31:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
x = max(x, y);
}
template <typename T>
void chkmin(T &x, const T &y) {
x = min(x, y);
}
constexpr int MAXN = 2e5 + 10, MAXM = 6e5 + 10;
int n, m, q, a[MAXN][3], b[MAXN][3], lim[MAXN];
ull val[MAXN], pa[MAXM], pb[MAXM];
mt19937_64 rng;
unordered_map<ull, int> mp;
void update(ull x, int y) {
auto it = mp.find(x);
if (it != mp.end()) {
it->second += y;
if (!it->second) mp.erase(it);
} else {
mp[x] = y;
}
}
void insert(int p) {
for (auto i : a[p]) {
update(pa[i], -1);
pa[i] ^= val[p];
update(pa[i], 1);
}
for (auto i : b[p]) {
update(pb[i], 1);
pb[i] ^= val[p];
update(pb[i], -1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) val[i] = rng();
for (int i = 1; i <= n; ++i)
for (auto &j : a[i]) cin >> j;
for (int i = 1; i <= n; ++i)
for (auto &j : b[i]) cin >> j;
for (int i = 1, j = 1; i <= n; ++i) {
insert(i);
while (!mp.empty()) insert(j++);
lim[i] = j;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << (l >= lim[r] ? "Yes" : "No") << "\n";
}
return 0;
}
/*
g++ A.cpp -o A -std=c++17 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9680kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9752kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 9676kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9676kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 11948kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9748kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 11680kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9964kb
Pretest #9:
score: 5
Accepted
time: 22ms
memory: 9744kb
Pretest #10:
score: 5
Accepted
time: 23ms
memory: 9772kb
Pretest #11:
score: 5
Accepted
time: 149ms
memory: 12092kb
Pretest #12:
score: 5
Accepted
time: 159ms
memory: 12532kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 9932kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 9860kb
Pretest #15:
score: 5
Accepted
time: 113ms
memory: 9764kb
Pretest #16:
score: 5
Accepted
time: 105ms
memory: 11832kb
Pretest #17:
score: 5
Accepted
time: 12ms
memory: 11828kb
Pretest #18:
score: 5
Accepted
time: 15ms
memory: 10616kb
Pretest #19:
score: 5
Accepted
time: 276ms
memory: 10960kb
Pretest #20:
score: 5
Accepted
time: 283ms
memory: 19956kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9748kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9764kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9764kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9696kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9980kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9696kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9696kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9900kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 9748kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 9768kb
Test #11:
score: 5
Accepted
time: 145ms
memory: 11304kb
Test #12:
score: 5
Accepted
time: 154ms
memory: 12380kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 11816kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 9780kb
Test #15:
score: 5
Accepted
time: 119ms
memory: 9756kb
Test #16:
score: 5
Accepted
time: 106ms
memory: 9864kb
Test #17:
score: 5
Accepted
time: 15ms
memory: 9912kb
Test #18:
score: 5
Accepted
time: 16ms
memory: 12668kb
Test #19:
score: 5
Accepted
time: 259ms
memory: 11816kb
Test #20:
score: 5
Accepted
time: 282ms
memory: 19940kb
Extra Test:
score: 0
Extra Test Passed