QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252847 | #7626. Quake and Rebuild | ucup-team004 | WA | 228ms | 3836kb | C++20 | 4.2kb | 2023-11-16 13:23:40 | 2023-11-16 13:23:41 |
Judging History
你现在查看的是最新测评结果
- [2024-11-20 20:27:49]
- hack成功,自动添加数据
- (/hack/1219)
- [2023-12-04 09:28:18]
- hack成功,自动添加数据
- (//qoj.ac/hack/477)
- [2023-11-16 13:23:40]
- 提交
answer
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> p(n);
p[0] = -1;
for (int i = 1; i < n; i++) {
std::cin >> p[i];
p[i]--;
}
const int B = std::sqrt(n);
const int nb = (n + B - 1) / B;
std::vector<int> tag(nb);
std::vector<int> fin(nb);
std::vector<int> top(n), dep(n);
auto build = [&](int b) {
if (fin[b]) {
return;
}
int l = b * B, r = std::min(n, l + B);
fin[b] = 1;
for (int i = std::max(1, l); i < r; i++) {
int P = std::max(p[i] - tag[b], 0);
if (P < l) {
top[i] = i, dep[i] = 0;
} else {
top[i] = top[P], dep[i] = dep[P] + 1;
fin[b] = 0;
}
}
};
for (int i = 0; i < nb; i++) {
build(i);
}
std::vector<int> f(n), tmp(n);
std::vector<std::vector<int>> bl(nb);
while (m--) {
int o;
std::cin >> o;
if (o == 1) {
int l, r, d;
std::cin >> l >> r >> d;
l--, r--;
int lb = l / B, rb = r / B;
if (lb == rb) {
for (int i = l; i <= r; i++) {
p[i] -= 1;
}
build(lb);
} else {
for (int i = l; i < (lb + 1) * B; i++) {
p[i] -= 1;
}
build(lb);
for (int i = lb + 1; i < rb; i++) {
tag[i] += 1;
build(i);
}
for (int i = rb * B; i <= r; i++) {
p[i] -= 1;
}
build(rb);
}
} else {
int k;
std::cin >> k;
int mn = n;
std::vector<int> a(k);
for (int i = 0; i < k; i++) {
std::cin >> a[i];
a[i]--;
mn = std::min(mn, a[i]);
if (!f[a[i]]) {
f[a[i]] = 1;
bl[a[i] / B].push_back(a[i]);
}
}
int ans = 1;
for (int b = nb - 1; b >= 0; b--) {
if (bl[b].empty()) {
continue;
}
int dup = 0;
for (auto x : bl[b]) {
dup |= tmp[top[x]];
tmp[top[x]] = 1;
}
for (auto x : bl[b]) {
tmp[top[x]] = 0;
}
if (dup) {
for (int x = std::min(n, (b + 1) * B) - 1; x >= b * B; x--) {
if (f[x]) {
f[x] = 0;
if (x == mn) {
break;
}
int y = std::max(0, p[x] - tag[b]);
ans += 1;
mn = std::min(mn, y);
if (!f[y]) {
f[y] = 1;
bl[y / B].push_back(y);
}
}
}
} else {
if (bl[b].size() == 1 && mn == bl[b][0]) {
bl[b].clear();
f[mn] = 0;
break;
}
for (auto x : bl[b]) {
ans += dep[x] + 1;
f[x] = 0;
int y = std::max(p[top[x]] - tag[b], 0);
mn = std::min(mn, y);
if (!f[y]) {
f[y] = 1;
bl[y / B].push_back(y);
}
}
bl[b].clear();
}
}
std::cout << ans << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 3768kb
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: -100
Wrong Answer
time: 228ms
memory: 3836kb
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:
88 84 91 80 79 71 79 78 65 69 66 68 67 69 59 69 68 64 59 62 60 56 59 61 57 58 57 50 58 55 57 63 53 56 52 54 52 51 52 52 52 57 52 56 50 51 50 52 51 53 53 53 53 52 53 48 54 53 49 51 48 49 56 52 53 53 52 49 51 47 51 50 51 46 54 51 47 49 51 49 47 47 50 51 49 53 51 52 51 51 49 49 51 53 50 50 52 53 49 51 ...
result:
wrong answer 1st lines differ - expected: '78', found: '88'