QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662368 | #7626. Quake and Rebuild | nhuang685 | TL | 2887ms | 4464kb | C++23 | 4.6kb | 2024-10-20 23:19:20 | 2024-10-20 23:19:25 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-10-19 17:11:02
*
*
*/
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
namespace rs = std::ranges;
namespace rv = std::views;
constexpr int BL = 450;
int start(int val) { return val / BL * BL; }
int end(int val) { return (val / BL + 1) * BL - 1; }
struct Arr {
std::vector<int> arr, la;
Arr() = default;
explicit Arr(int n) : arr(n), la(n / BL) {}
void add(int i, int v) { arr[i] += v; }
void set(int i, int v) { arr[i] = v - la[i / BL]; }
void add_i(int i, int v) { la[i] += v; }
int get(int i) const { return std::max(0, arr[i] + la[i / BL]); }
int operator[](int i) const { return get(i); }
};
struct RBArr {
std::vector<int> arr, la;
RBArr() = default;
explicit RBArr(int n) : arr(n) {}
void add(int i, int v) {
if (arr[i] == 0) {
la.push_back(i);
}
arr[i] += v;
}
void set(int i, int v) {
if (arr[i] == 0) {
la.push_back(i);
}
arr[i] = v;
}
const int& operator[](int i) const { return arr[i]; }
void reset() {
for (int i : la) {
arr[i] = 0;
}
la.clear();
}
};
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int nn, m;
std::cin >> nn >> m;
int n = (nn + BL - 1) / BL * BL;
Arr fa(n), nxt(n);
for (int i = 1; i < nn; ++i) {
int v;
std::cin >> v;
--v;
fa.set(i, v);
}
std::vector<int> cnt(n);
auto recomp = [&](int ind) {
for (int i = BL * ind; i < BL * (ind + 1); ++i) {
if (fa[i] < BL * ind) {
nxt.set(i, fa[i]);
cnt[i] = 1;
} else {
nxt.set(i, nxt[fa[i]]);
cnt[i] = cnt[fa[i]] + 1;
}
}
cnt[BL * ind] = 1;
};
for (int i = 1; i < n / BL; ++i) {
recomp(i);
}
auto sub = [&](int l, int r, int d) {
if (l / BL == r / BL) {
for (int i = l; i <= r; ++i) {
fa.add(i, -d);
}
recomp(l / BL);
return;
}
for (int i = l; i <= end(l); ++i) {
fa.add(i, -d);
}
recomp(l / BL);
for (int i = end(l) + 1; i < start(r); i += BL) {
bool re = fa.la[i / BL] < BL;
fa.add_i(i / BL, -d);
if (re) {
recomp(i / BL);
} else {
nxt.add_i(i / BL, -d);
}
}
for (int i = start(r); i <= r; ++i) {
fa.add(i, -d);
}
recomp(r / BL);
};
auto lca = [&](int a, int b) {
while (nxt[a] != nxt[b]) {
if (a < b) {
std::swap(a, b);
}
a = nxt[a];
}
if (a / BL != b / BL) {
return nxt[a];
}
while (a != b) {
if (a < b) {
std::swap(a, b);
}
a = fa[a];
}
return a;
};
RBArr freq(n);
auto query = [&](const std::vector<int>& b) -> int {
int l = b[0];
for (int i = 1; i < std::ssize(b); ++i) {
l = lca(l, b[i]);
}
std::vector<std::vector<int>> gr(n / BL);
for (int i : b) {
gr[i / BL].push_back(i);
}
int ans = 0;
for (int i = n / BL - 1; i >= 0 && l <= (i + 1) * BL - 1; --i) {
if (gr[i].empty()) {
continue;
}
freq.reset();
std::vector<int> ele;
for (int j : gr[i]) {
freq.add(j, 1);
if (freq[j] == 1) {
ele.push_back(j);
}
}
freq.reset();
bool two = false;
for (int j : ele) {
freq.add(nxt[j], 1);
if (freq[nxt[j]] >= 2) {
two = true;
}
}
if (!two && l < i * BL) {
for (int j : ele) {
gr[nxt[j] / BL].push_back(nxt[j]);
ans += cnt[j];
}
continue;
}
freq.reset();
for (int j : ele) {
freq.add(j, 1);
}
for (int j = (i + 1) * BL - 1; j >= std::max(l, i * BL); --j) {
if (freq[j] == 0) {
continue;
}
++ans;
if (fa[j] >= i * BL) {
freq.add(fa[j], 1);
} else {
gr[fa[j] / BL].push_back(fa[j]);
}
}
}
return ans;
};
while ((m--) != 0) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, d;
std::cin >> l >> r >> d;
--l;
--r;
sub(l, r, d);
} else {
int k;
std::cin >> k;
std::vector<int> b(k);
for (int& i : b) {
std::cin >> i;
--i;
}
std::cout << query(b) << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 592ms
memory: 3700kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 78 70 64 60 55 60 58 52 54 51 53 56 51 51 57 55 52 49 55 49 50 53 49 49 48 49 48 53 50 50 54 47 52 45 49 49 46 47 48 49 50 48 49 47 48 47 49 48 50 48 49 48 47 49 48 51 48 48 45 45 46 50 50 50 48 49 46 47 47 46 48 48 47 49 47 46 47 46 47 46 45 47 49 49 50 51 48 48 49 47 47 48 50 46 47 48 50 46 47 ...
result:
ok 13214 lines
Test #4:
score: 0
Accepted
time: 767ms
memory: 3832kb
input:
6173 198631 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2819 1049 1155 831 722 5962 123 624 554 601 241 597 81 29 34 390 350 443 385 6038 6083 258 5 315 27 281 6029 300 6136 322 227 46 271 263 26 268 257 6101 5816 255 258 156 243 270 186 6099 16 13 5435 163 7 35 219 182 214 10 24 23 194 178 188 183 200 167 158 197 24 189 131 35 167 24 189 15 183 176 6050...
result:
ok 30261 lines
Test #5:
score: 0
Accepted
time: 963ms
memory: 3804kb
input:
9724 198809 1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...
output:
24 25 31 31 27 25 29 23 23 21 26 23 21 24 23 23 26 26 21 24 27 23 23 23 20 19 20 18 28 25 26 21 19 21 21 26 20 23 17 20 18 21 22 22 18 21 25 18 17 18 24 18 16 18 19 24 20 18 19 17 17 21 25 19 21 23 19 23 15 17 19 19 22 18 20 18 21 19 18 18 15 16 22 17 17 18 13 16 19 16 15 16 18 16 15 17 15 18 18 20 ...
result:
ok 66269 lines
Test #6:
score: 0
Accepted
time: 1445ms
memory: 3996kb
input:
12796 185791 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
12100 7532 12357 12774 211 12761 5309 1646 12726 1882 247 118 1660 12229 12143 1499 1368 1273 1387 341 274 1374 1237 1359 112 1152 981 12681 949 890 820 774 62 644 836 925 12 13 1203 666 732 731 1127 12320 11473 82 655 12788 569 5866 621 2798 12114 85 609 11827 1 12455 56 605 575 530 54 645 1845 93 ...
result:
ok 3210 lines
Test #7:
score: 0
Accepted
time: 1881ms
memory: 3912kb
input:
16122 194030 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...
output:
9730 7096 4371 4171 3732 3716 3273 2910 2530 2423 2366 2351 2013 2196 2430 1891 1833 1852 1638 1709 1762 1699 1423 1295 1471 1255 1356 1428 1214 1191 1066 1104 1131 1116 1010 860 964 949 927 994 879 829 718 787 786 754 757 795 820 739 761 689 659 658 587 663 654 658 631 593 633 583 575 598 554 579 4...
result:
ok 9701 lines
Test #8:
score: 0
Accepted
time: 1996ms
memory: 4228kb
input:
19492 191214 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 1 2 10 10 1 2 2 1 1 1 1 2 1 2 2 4 3 1 1 4 10 2 5 6 1 1 6 11 3 7 1 6 5 4 8 8 12 2 4 5 6 1 2 4 10 4 8 15 3 1 15 1 1 4 9 6 9 2 2 11 3 6 11 17 6 6 2 5 10 8 3 3 4 2 1 3 3 12 1 14 1 1 6 1 5 7 23 7 12 8 13 1 11 13 6 22 3 20 2 8 4 1 41 5 3 27 13 15 4 4 6 9 ...
output:
207 284 264 237 41 207 17559 198 186 201 168 1 1461 9 218 170 156 191 7 195 189 177 165 18623 170 25 151 18433 168 181 164 179 188 18572 1 171 172 182 137 179 184 127 162 166 167 171 17 147 180 165 175 173 167 1359 20 161 138 175 169 176 178 6 152 178 7 121 16 12 4 9 8 5 4 6 29 6 7 10 42 5 3 1 5 27 ...
result:
ok 18556 lines
Test #9:
score: 0
Accepted
time: 2174ms
memory: 3956kb
input:
22808 195820 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 3 2 1 2 4 4 1 2 1 5 4 1 4 2 1 3 1 1 3 1 4 3 4 5 15 1 6 10 1 1 3 1 1 1 1 3 5 7 4 2 3 15 4 4 1 11 1 2 5 2 2 12 4 3 1 9 6 4 2 1 3 5 5 1 4 1 2 16 15 1 6 1 10 1 9 6 9 2 1 12 6 2 13 2 3 1 8 17 2 8 1 16 5 28 4 24 2 9 5 1 11 18 15 6 7 10 3 1 1 11 8 1 12 4 7 1...
output:
42 45 42 45 40 47 43 37 38 41 37 44 42 38 42 34 34 32 37 37 37 39 35 45 35 40 32 36 43 34 33 39 29 32 33 33 33 31 28 32 35 31 23 33 31 30 26 34 28 30 35 32 32 30 33 28 26 29 30 26 24 27 25 28 22 30 26 27 23 29 31 25 27 30 26 26 33 30 27 26 21 32 27 28 28 25 31 26 24 24 24 23 30 22 26 21 26 27 24 22 ...
result:
ok 39164 lines
Test #10:
score: 0
Accepted
time: 2722ms
memory: 4464kb
input:
26352 183295 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 1 2 2 1 1 1 2 11 1 2 1 4 1 2 3 1 3 3 4 2 3 2 5 3 2 1 2 1 3 6 1 2 3 1 6 3 2 4 3 1 7 3 6 3 10 1 1 2 5 1 1 7 3 2 3 3 8 7 2 5 9 2 3 1 9 3 1 2 8 7 5 1 2 1 1 11 5 2 3 8 3 7 4 1 6 5 1 10 16 11 3 4 3 6 14 4 3 15 27 14 2 3 5 6 14 15 11 21 2 3 2 1...
output:
25212 25 316 497 330 4 314 304 24633 297 285 5 252 26284 11 256 281 275 26265 12 1 14 17 12 6 12 5 10 3 15 9 7 10 1 1 9 9 3 40 11 10 19 9 9 9 14 4 17 3 8 13 5 6 9 32 12 6 4 6 3 4 4 1 4 1991 29 40 1 5 30 911 3 9 11 44 45 3 1 15 1 16 9 16 14 3 15 31 15 1 7 14 367 3479 5 4 14 6 25 13 4 7 3 5 14 18 8 13...
result:
ok 3811 lines
Test #11:
score: 0
Accepted
time: 2887ms
memory: 4120kb
input:
27196 199560 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 3 2 4 1 1 2 4 1 2 1 2 5 3 5 4 1 1 2 4 1 2 11 4 2 7 1 1 3 1 1 2 2 5 2 2 6 1 3 3 2 4 7 2 5 3 2 6 10 4 2 6 3 2 1 2 2 17 1 1 2 5 9 5 4 19 12 2 12 3 2 19 4 4 12 7 6 5 9 3 2 6 3 13 1 1 11 9 6 14 9 3 3 4 17 6 1 5 13 3 1 32 15 26 3 1 2 15 3 1 4 14 2 7 2 1...
output:
82 78 77 73 75 72 69 68 65 65 63 59 65 60 65 71 58 67 64 64 62 61 62 67 46 61 54 60 56 55 51 52 45 47 54 51 49 45 53 45 53 46 43 41 42 51 48 48 43 40 44 45 42 47 43 40 42 51 44 44 42 44 43 39 43 42 40 41 44 41 39 41 39 42 36 41 42 38 42 38 42 42 44 40 44 45 35 37 38 38 40 37 38 42 42 41 35 40 39 37 ...
result:
ok 19956 lines
Test #12:
score: -100
Time Limit Exceeded
input:
32698 192710 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...