QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#535738 | #9155. 集合 | December456 | 100 ✓ | 296ms | 33232kb | C++14 | 2.7kb | 2024-08-28 14:06:38 | 2024-08-28 14:06:39 |
Judging History
answer
#include <cstdio>
#include <vector>
constexpr int MAXN = 200000 + 2;
constexpr int MAXM = MAXN * 3;
constexpr int MAXQ = MAXN * 5;
constexpr int HASH_P[2] = {1000000993, 1000000933};
constexpr int HASH_BASE[2] = {783763, 997991};
constexpr int SQRT_HASH_P = 31623;
template <int B, int P> class QuickPower {
public:
int big[SQRT_HASH_P], small[SQRT_HASH_P];
QuickPower() {
big[0] = small[0] = 1;
for (int i = 1; i < SQRT_HASH_P; i ++) {
small[i] = (long long){small[i - 1]} * B % P;
}
for (int i = 1, b = small[SQRT_HASH_P - 1]; i < SQRT_HASH_P; i ++) {
big[i] = (long long){big[i - 1]} * b % P;
}
}
int operator ()(int x) const {
return (long long){big[x / SQRT_HASH_P]} * small[x % SQRT_HASH_P] % P;
}
};
template <int _type> class Hash {
public:
static QuickPower<HASH_BASE[_type], HASH_P[_type]> pw;
int val;
template <int _t> Hash& operator +=(const Hash<_t> &rhs) {
val = (val + pw(rhs.val)) % HASH_P[_type];
return *this;
}
template <int _t> Hash& operator -=(const Hash<_t> &rhs) {
val = (val + HASH_P[_type] - pw(rhs.val)) % HASH_P[_type];
return *this;
}
bool operator !=(const Hash &rhs) {
return val != rhs.val;
}
};
template <int _type> QuickPower<HASH_BASE[_type], HASH_P[_type]> Hash<_type>::pw;
Hash<0> ph[MAXM][2];
Hash<1> th[2];
int a[MAXM], b[MAXM];
bool ans[MAXQ];
std::vector<std::pair<int, int>> qry[MAXN];
void remove(int v, int x, int o) {
th[o] -= ph[v][o];
ph[v][o] -= Hash<0>{x};
th[o] += ph[v][o];
}
void insert(int v, int x, int o) {
th[o] -= ph[v][o];
ph[v][o] += Hash<0>{x};
th[o] += ph[v][o];
}
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
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 i = 0, l, r; i < q; i ++) {
scanf("%d%d", &l, &r);
qry[r].push_back({l, i});
}
for (int l = 1, r = 1; r <= n; r ++) {
for (int i = 0; i < 3; i ++) {
insert(a[r * 3 - i], r, 0);
insert(b[r * 3 - i], r, 1);
}
while (th[0] != th[1]) {
for (int i = 0; i < 3; i ++) {
remove(a[l * 3 - i], l, 0);
remove(b[l * 3 - i], l, 1);
}
l ++;
}
for (auto pr : qry[r]) {
ans[pr.second] = pr.first >= l;
}
}
for (int i = 0; i < q; i ++) {
puts(ans[i] ? "Yes" : "No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 13316kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 13132kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 12944kb
Pretest #4:
score: 5
Accepted
time: 3ms
memory: 13084kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 13188kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 12780kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 12228kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 12956kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 14584kb
Pretest #10:
score: 5
Accepted
time: 22ms
memory: 14084kb
Pretest #11:
score: 5
Accepted
time: 124ms
memory: 18248kb
Pretest #12:
score: 5
Accepted
time: 123ms
memory: 19880kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 13820kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 12940kb
Pretest #15:
score: 5
Accepted
time: 117ms
memory: 24064kb
Pretest #16:
score: 5
Accepted
time: 119ms
memory: 22992kb
Pretest #17:
score: 5
Accepted
time: 9ms
memory: 14232kb
Pretest #18:
score: 5
Accepted
time: 9ms
memory: 12612kb
Pretest #19:
score: 5
Accepted
time: 265ms
memory: 30344kb
Pretest #20:
score: 5
Accepted
time: 287ms
memory: 33168kb
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 13276kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 12484kb
Test #3:
score: 5
Accepted
time: 3ms
memory: 12944kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 13588kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 12324kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 13568kb
Test #7:
score: 5
Accepted
time: 3ms
memory: 13352kb
Test #8:
score: 5
Accepted
time: 3ms
memory: 13500kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 14532kb
Test #10:
score: 5
Accepted
time: 17ms
memory: 14020kb
Test #11:
score: 5
Accepted
time: 108ms
memory: 19496kb
Test #12:
score: 5
Accepted
time: 105ms
memory: 19876kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 12404kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 12844kb
Test #15:
score: 5
Accepted
time: 111ms
memory: 23636kb
Test #16:
score: 5
Accepted
time: 109ms
memory: 24260kb
Test #17:
score: 5
Accepted
time: 8ms
memory: 14044kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 14148kb
Test #19:
score: 5
Accepted
time: 281ms
memory: 28952kb
Test #20:
score: 5
Accepted
time: 296ms
memory: 33232kb
Extra Test:
score: 0
Extra Test Passed