백준16670 King Kog's Reception

작성일 | In

문제 링크

  • http://icpc.me/16670

문제 출처

  • 2018 NEERC K번

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(Q log N)

풀이

세그먼트 트리의 노드를 아래와 같이 정의해봅시다.

1
2
3
struct Node{
  long long sum, max;
}

sum은 양쪽 자식의 소요시간의 합, max는 양쪽 자식의 작업이 끝나는 시간을 나타냅니다.
두 개의 노드를 합치는(부모 노드의 결과를 뽑아내는) 코드는 아래와 같이 짤 수 있습니다.

1
2
3
4
void push(int node){
  tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
  tree[node].max = max(tree[node*2+1].max, tree[node*2].max + tree[node*2+1].sum);
}

sum은 단순히 구해주면 되고, max는 오른쪽 자식의 작업이 끝나는 시간과, 왼쪽 자식의 작업을 끝내고 오른쪽 자식의 작업을 수행하는 시간 중 최댓값을 취해주면 됩니다.

이 부분만 알고 있다면 어렵지 않게 구현할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll ans;

struct Node{
	ll sum, max;
};

Node tree[4040404];

void push(int node){
	tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
    tree[node].max = max(tree[node*2+1].max, tree[node*2].max + tree[node*2+1].sum);
}

void init(int node, int s, int e){
    if(s == e){
        tree[node].sum=0, tree[node].max = s;
        return;
    }
    int m = s + e >> 1;
    init(node*2, s, m);
    init(node*2+1, m+1, e);
    push(node);
}
void update(int node, int s, int e, int x, ll v){
    if(s == e){
    	tree[node].sum += v;
    	tree[node].max += v;
        return;
    }
    int m = s + e >> 1;
    if(x <= m) update(node*2, s, m, x, v);
    else update(node*2+1, m+1, e, x, v);
    push(node);

}

void query(int node, int s, int e, int x){
    if(e <= x){
        ans = max(tree[node].max, ans + tree[node].sum);
        return;
    }
    int m = s + e >> 1;
    query(node*2, s, m, x);
    if(m < x) query(node*2+1, m+1, e, x);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; vector<p> v(n+1);
	init(1, 1, 1000000);

	for(int i=1; i<=n; i++){
		char op; ll a, b; cin >> op;
		if(op == '+'){
			cin >> a >> b;
			v[i] = {a, b};
			update(1, 1, 1000000, a, b);
		}else if(op == '-'){
			cin >> a;
			update(1, 1, 1000000, v[a].first, -v[a].second);
		}else{
			cin >> a;
			ans = 0; query(1, 1, 1000000, a);
			cout << max(ans - a, 0LL) << "\n";
		}
	}
}