백준 16670번: King Kog's Reception [C++]

작성일 | In
다이아몬드 V 다이아몬드 V

문제

King Kog’s Reception

풀이

Join으로 주어지는 시간들을 $t_i$, $d_i$라 하고 Query로 주어지는 시간을 $t_q$라 합시다.

우리는 $t_i \le t_q$를 만족하는 모든 Join이 끝나는 시간을 찾으면 됩니다.

먼저 정답 ans = 0으로 초기화합니다. 그리고 $t_i$가 작은 것 부터 순서대로 ans = max(t_i + d_i, ans + d_i)를 적용하면 답을 찾을 수 있습니다.

max에서 첫 번째 인자는 ans < t_i라 Join이 겹치지 않아서 밀리지 않은 경우이고, 두 번째 인자는 ans > t_i라 Join들이 겹쳐서 밀린 경우입니다.

이를 Naive하게 계산하면 $O(q)$가 걸리지만 세그먼트 트리를 이용하면 $O(\log 10^6)$에 계산할 수 있습니다.

세그먼트 트리의 노드에 두 가지 값을 관리합니다. 하나는 해당 구간에서 모든 Join이 끝나는 시간, 두 번째는 해당 구간의 $d_i$의 합입니다. 이는 위에서 말한 ans를 계산하는 식과 같은 방식으로 계산할 수 있습니다.

코드

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

using ll = long long;

struct SegmentTree {
    struct Node {
        ll sum, maxEnd;
    };
    Node merge(Node& left, Node& right) {
        Node ret;

        ret.sum = left.sum + right.sum;
        ret.maxEnd = max(left.maxEnd + right.sum, right.maxEnd);

        return ret;
    }

    vector<Node> t;

    SegmentTree(int n) : t(1 << (int)(ceil(log2(n)) + 1)) { init(1, 1, n); }
    void init(int node, int s, int e) {
        if (s == e) {
            t[node] = Node(0, s);
            return;
        }

        int m = (s + e) / 2;
        init(node << 1, s, m);
        init(node << 1 | 1, m + 1, e);
        t[node] = merge(t[node << 1], t[node << 1 | 1]);
    }

    void change(int node, int s, int e, int i, int v) {
        if (s == e) {
            t[node] = Node(v, s + v);
            return;
        }

        int m = (s + e) / 2;
        if (i <= m)
            change(node << 1, s, m, i, v);
        else
            change(node << 1 | 1, m + 1, e, i, v);

        t[node] = merge(t[node << 1], t[node << 1 | 1]);
    }

    ll query(int node, int s, int e, int i) {
        ll ret = 0;

        while (s < e) {
            int m = (s + e) / 2;

            if (i <= m) {
                node = node << 1;
                e = m;
                continue;
            }

            ret = max(t[node << 1].maxEnd, ret + t[node << 1].sum);
            node = node << 1 | 1;
            s = m + 1;
        }
        ret = max(t[node].maxEnd, ret + t[node].sum);

        return ret;
    }
};

const int MAX_TIME = 1e6;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    SegmentTree tree(MAX_TIME);

    int q;
    cin >> q;

    vector<int> joinTime(q + 1);

    for (int k = 1; k <= q; k++) {
        char type;
        cin >> type;

        if (type == '+') {
            int t, d;
            cin >> t >> d;

            joinTime[k] = t;
            tree.change(1, 1, MAX_TIME, t, d);
        } else if (type == '-') {
            int i;
            cin >> i;

            tree.change(1, 1, MAX_TIME, joinTime[i], 0);
        } else {
            int t;
            cin >> t;

            println("{}", max(tree.query(1, 1, MAX_TIME, t) - t, 0LL));
        }
    }

    return 0;
}

백준 16670번: King Kog's Reception [C++]