QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252847#7626. Quake and Rebuilducup-team004WA 228ms3836kbC++204.2kb2023-11-16 13:23:402023-11-16 13:23:41

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2023-11-16 13:23:41]
  • 评测
  • 测评结果:WA
  • 用时:228ms
  • 内存:3836kb
  • [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;
}

详细

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'