QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488492 | #9155. 集合 | liyelin | 100 ✓ | 748ms | 103680kb | C++14 | 2.6kb | 2024-07-24 08:29:27 | 2024-07-24 08:29:27 |
Judging History
answer
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (int i = (r); i >= (l); --i)
#define FI first
#define SE second
#define SZ size()
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 5;
const int M = 6e5 + 5;
const ull P = 1e9 + 9;
int n, mn[N], m, q, a[N][3], b[N][3], cnt;
ull pw[N], ha[M], hb[M];
unordered_map<ull, int> A, B;
unordered_map<ull, bool> qc;
void clean_up(int x, int k) {
qc.clear();
FOR (i, 0, 2) {
int s = a[x][i];
if (!qc[ha[s]]) {
qc[ha[s]] = 1;
cnt += (A[ha[s]] != B[ha[s]]) * k;
}
s = b[x][i];
if (!qc[hb[s]]) {
qc[hb[s]] = 1;
cnt += (A[hb[s]] != B[hb[s]]) * k;
}
}
}
void add(int x) {
clean_up(x, -1);
FOR (i, 0, 2) {
A[ha[a[x][i]]]--;
B[hb[b[x][i]]]--;
}
clean_up(x, 1);
FOR (i, 0, 2) {
int s = a[x][i];
ha[s] -= pw[x];
s = b[x][i];
hb[s] -= pw[x];
}
clean_up(x, -1);
FOR (i, 0, 2) {
A[ha[a[x][i]]]++;
B[hb[b[x][i]]]++;
}
clean_up(x, 1);
}
void sub(int x) {
clean_up(x, -1);
FOR (i, 0, 2) {
A[ha[a[x][i]]]--;
B[hb[b[x][i]]]--;
}
clean_up(x, 1);
FOR (i, 0, 2) {
int s = a[x][i];
ha[s] += pw[x];
s = b[x][i];
hb[s] += pw[x];
}
clean_up(x, -1);
FOR (i, 0, 2) {
A[ha[a[x][i]]]++;
B[hb[b[x][i]]]++;
}
clean_up(x, 1);
}
void solve() {
int l = 1;
ull all = 0;
FOR (i, 1, n) all += pw[i];
A[all] = B[all] = m;
FOR (i, 1, m) ha[i] = hb[i] = all;
FOR (r, 1, n) {
add(r);
// FOR (i, 1, m) {
// cout << ha[i] << ' ';
// }
// cout << '\n';
// FOR (i, 1, m) {
// cout << hb[i] << ' ';
// }
// cout << '\n';
// cout << cnt << '\n';
while (cnt > 0) sub(l++);
mn[r] = l;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
pw[0] = 1;
FOR (i, 1, n) pw[i] = pw[i - 1] * P;
FOR (i, 1, n) {
FOR (j, 0, 2) {
cin >> a[i][j];
}
}
FOR (i, 1, n) {
FOR (j, 0, 2) {
cin >> b[i][j];
}
}
solve();
FOR (i, 1, q) {
int l, r;
cin >> l >> r;
if (mn[r] <= l) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 13880kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 13904kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 13840kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9756kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 13792kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 11864kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 11816kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 11856kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 12096kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 10120kb
Pretest #11:
score: 5
Accepted
time: 621ms
memory: 103680kb
Pretest #12:
score: 5
Accepted
time: 635ms
memory: 99768kb
Pretest #13:
score: 5
Accepted
time: 6ms
memory: 12544kb
Pretest #14:
score: 5
Accepted
time: 5ms
memory: 14540kb
Pretest #15:
score: 5
Accepted
time: 106ms
memory: 12608kb
Pretest #16:
score: 5
Accepted
time: 98ms
memory: 12688kb
Pretest #17:
score: 5
Accepted
time: 49ms
memory: 21012kb
Pretest #18:
score: 5
Accepted
time: 42ms
memory: 24216kb
Pretest #19:
score: 5
Accepted
time: 748ms
memory: 101152kb
Pretest #20:
score: 5
Accepted
time: 686ms
memory: 97320kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 11836kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 10052kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 14140kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 12100kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 11800kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9816kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 14172kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 13852kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 11872kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 12092kb
Test #11:
score: 5
Accepted
time: 631ms
memory: 99964kb
Test #12:
score: 5
Accepted
time: 574ms
memory: 95108kb
Test #13:
score: 5
Accepted
time: 6ms
memory: 12600kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 12536kb
Test #15:
score: 5
Accepted
time: 115ms
memory: 12604kb
Test #16:
score: 5
Accepted
time: 101ms
memory: 10584kb
Test #17:
score: 5
Accepted
time: 39ms
memory: 22852kb
Test #18:
score: 5
Accepted
time: 42ms
memory: 22736kb
Test #19:
score: 5
Accepted
time: 721ms
memory: 98036kb
Test #20:
score: 5
Accepted
time: 686ms
memory: 98272kb
Extra Test:
score: 0
Extra Test Passed