QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505666 | #9155. 集合 | 251Sec | 100 ✓ | 460ms | 61204kb | C++14 | 1.3kb | 2024-08-05 08:06:12 | 2024-08-05 08:06:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 eng(363415);
int n, m, q;
unordered_map<ll, int> f;
int g;
void UpdCnt(ll p, int x) {
if (f[p]) g--;
f[p] += x;
if (f[p]) g++;
}
int a[600005], b[600005];
ull fa[600005], fb[600005], w[600005];
void Upd(int p, int x) {
UpdCnt(fa[a[p * 3 - 2]], -1), UpdCnt(fa[a[p * 3 - 1]], -1), UpdCnt(fa[a[p * 3]], -1);
fa[a[p * 3 - 2]] += w[p] * x;
fa[a[p * 3 - 1]] += w[p] * x;
fa[a[p * 3]] += w[p] * x;
UpdCnt(fa[a[p * 3 - 2]], 1), UpdCnt(fa[a[p * 3 - 1]], 1), UpdCnt(fa[a[p * 3]], 1);
UpdCnt(fb[b[p * 3 - 2]], 1), UpdCnt(fb[b[p * 3 - 1]], 1), UpdCnt(fb[b[p * 3]], 1);
fb[b[p * 3 - 2]] += w[p] * x;
fb[b[p * 3 - 1]] += w[p] * x;
fb[b[p * 3]] += w[p] * x;
UpdCnt(fb[b[p * 3 - 2]], -1), UpdCnt(fb[b[p * 3 - 1]], -1), UpdCnt(fb[b[p * 3]], -1);
}
int ans[600005];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) w[i] = eng();
for (int i = 1; i <= n * 3; i++) scanf("%d", a + i);
for (int i = 1; i <= n * 3; i++) scanf("%d", b + i);
for (int r = 1, l = 1; r <= n; r++) {
Upd(r, 1);
while (g) Upd(l++, -1);
ans[r] = l;
}
while (q--) {
int l, r; scanf("%d%d", &l, &r);
puts(l >= ans[r] ? "Yes" : "No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 9768kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9764kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9808kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 10104kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 10100kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9872kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9864kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9852kb
Pretest #9:
score: 5
Accepted
time: 21ms
memory: 10096kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 9864kb
Pretest #11:
score: 5
Accepted
time: 354ms
memory: 58180kb
Pretest #12:
score: 5
Accepted
time: 350ms
memory: 56824kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 10220kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10228kb
Pretest #15:
score: 5
Accepted
time: 98ms
memory: 10264kb
Pretest #16:
score: 5
Accepted
time: 103ms
memory: 10296kb
Pretest #17:
score: 5
Accepted
time: 24ms
memory: 16204kb
Pretest #18:
score: 5
Accepted
time: 22ms
memory: 15024kb
Pretest #19:
score: 5
Accepted
time: 449ms
memory: 57552kb
Pretest #20:
score: 5
Accepted
time: 443ms
memory: 61204kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9812kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9828kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9836kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10108kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9868kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 10092kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9844kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9904kb
Test #9:
score: 5
Accepted
time: 18ms
memory: 9840kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 9900kb
Test #11:
score: 5
Accepted
time: 350ms
memory: 56744kb
Test #12:
score: 5
Accepted
time: 347ms
memory: 54808kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 10160kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 10180kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 10152kb
Test #16:
score: 5
Accepted
time: 106ms
memory: 10280kb
Test #17:
score: 5
Accepted
time: 19ms
memory: 14080kb
Test #18:
score: 5
Accepted
time: 22ms
memory: 15000kb
Test #19:
score: 5
Accepted
time: 460ms
memory: 56456kb
Test #20:
score: 5
Accepted
time: 437ms
memory: 60648kb
Extra Test:
score: 0
Extra Test Passed