QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491101 | #9155. 集合 | zhenghanyun | 100 ✓ | 449ms | 61700kb | C++14 | 1.7kb | 2024-07-25 17:14:59 | 2024-07-25 17:14:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
mt19937_64 rng(time(NULL));
const int N = 2e5 + 5;
const int M = 6e5 + 5;
int n, m, q, cnt, a[N][3], b[N][3], ans[N];
ll w[N], hsh1[M], hsh2[M];
unordered_map <ll, int> mp;
inline void Add(ll pos, int val) {
if (mp[pos] == 0) {
++cnt;
}
mp[pos] += val;
if (mp[pos] == 0) {
--cnt;
}
}
inline void add(int i, ll val) {
Add(hsh1[a[i][0]], -1);
Add(hsh1[a[i][1]], -1);
Add(hsh1[a[i][2]], -1);
hsh1[a[i][0]] += val;
hsh1[a[i][1]] += val;
hsh1[a[i][2]] += val;
Add(hsh1[a[i][0]], 1);
Add(hsh1[a[i][1]], 1);
Add(hsh1[a[i][2]], 1);
Add(hsh2[b[i][0]], 1);
Add(hsh2[b[i][1]], 1);
Add(hsh2[b[i][2]], 1);
hsh2[b[i][0]] += val;
hsh2[b[i][1]] += val;
hsh2[b[i][2]] += val;
Add(hsh2[b[i][0]], -1);
Add(hsh2[b[i][1]], -1);
Add(hsh2[b[i][2]], -1);
}
int main() {
// assert(freopen("set.in", "r", stdin));
// assert(freopen("set.out", "w", stdout));
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i][0] >> b[i][1] >> b[i][2];
}
for (int i = 1; i <= n; ++i) {
w[i] = rng();
}
for (int i = 1; i <= n; ++i) {
if (i > 1) {
add(i - 1, -w[i - 1]);
}
ans[i] = ans[i - 1];
if (ans[i] < i) {
ans[i] = i;
add(i, w[i]);
}
while (ans[i] < n) {
add(ans[i] + 1, w[ans[i] + 1]);
if (cnt != 0) {
add(ans[i] + 1, -w[ans[i] + 1]);
break;
}
++ans[i];
}
}
while (q--) {
int l, r;
cin >> l >> r;
if (ans[l] >= r) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9984kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9836kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 10076kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 10060kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9828kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9900kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9880kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9856kb
Pretest #9:
score: 5
Accepted
time: 15ms
memory: 9880kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 10028kb
Pretest #11:
score: 5
Accepted
time: 349ms
memory: 61700kb
Pretest #12:
score: 5
Accepted
time: 327ms
memory: 56192kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 10472kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10504kb
Pretest #15:
score: 5
Accepted
time: 105ms
memory: 10176kb
Pretest #16:
score: 5
Accepted
time: 103ms
memory: 10300kb
Pretest #17:
score: 5
Accepted
time: 30ms
memory: 16308kb
Pretest #18:
score: 5
Accepted
time: 29ms
memory: 15020kb
Pretest #19:
score: 5
Accepted
time: 449ms
memory: 56520kb
Pretest #20:
score: 5
Accepted
time: 449ms
memory: 60336kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 9784kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 9832kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 9836kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9844kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9832kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9980kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9856kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9860kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 10108kb
Test #10:
score: 5
Accepted
time: 16ms
memory: 9892kb
Test #11:
score: 5
Accepted
time: 356ms
memory: 57824kb
Test #12:
score: 5
Accepted
time: 341ms
memory: 54572kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 10476kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 10296kb
Test #15:
score: 5
Accepted
time: 99ms
memory: 10172kb
Test #16:
score: 5
Accepted
time: 99ms
memory: 10248kb
Test #17:
score: 5
Accepted
time: 26ms
memory: 14284kb
Test #18:
score: 5
Accepted
time: 25ms
memory: 15072kb
Test #19:
score: 5
Accepted
time: 449ms
memory: 54788kb
Test #20:
score: 5
Accepted
time: 444ms
memory: 60720kb
Extra Test:
score: 0
Extra Test Passed