BOJ1933: 스카이라인

https://www.acmicpc.net/problem/1933

  • 일단 내가 푼 Up과 Down을 나눠서 multiset이나 map으로 푼게 가장 일반적인 풀이다.
  • 제일 빠른 풀이는 놀랍게도 분할정복 풀이. 생각지도 못했다. 분할정복은 나중에 따로 또 쭉 풀어봐야지.
  • 교훈: priority queue에서 값을 지워야 할 때는, pq 두개를 써서 해결할 수 있다.
    • MaxHeap일때
    • 지우는 전용 removePQ를 만들어놓고, 지워야 할때 removePQ에 넣자.
    • pq.top() == removePQ.top()이면 계속 빼서 지워준다.
    • 어짜피 Max만 관심있으므로, 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
#include <bits/stdc++.h>
using namespace std;

const int IN = 0, OUT = 1;
struct Node {
  int x, cmd, h;
  bool operator<(const Node &b) const {
    return x < b.x;
  }
};

class SkyLine {
  vector<Node> arr;

public:
  void input();
  void sweep();
};

void SkyLine::input() {
  int N, L, H, R;
  scanf("%d", &N);
  arr.reserve(2*N);
  for(int i = 0; i < N; i++) {
    scanf("%d%d%d", &L, &H, &R);
    arr.push_back({L, IN, H});
    arr.push_back({R, OUT, H});
  }
  arr.push_back({1000000001, IN, 0});
  sort(arr.begin(), arr.end());
}

void SkyLine::sweep() {
  map<int, int> heights;

  int prevX = arr[0].x, prevH = 0, cnt = 0;
  for(auto [x, cmd, h] : arr) {
    if(prevX != x) {
      int maxH = cnt ? heights.rbegin()->first : 0;
      if (maxH != prevH)
        printf("%d %d ", prevX, maxH);
      prevH = maxH;
    }

    if (cmd == IN) heights[h]++, cnt++;
    else {
      heights[h]--, cnt--;
      if(!heights[h]) heights.erase(h);
    }
    prevX = x;
  }
}

int main() {
  SkyLine sky;
  sky.input();
  sky.sweep();
}