백준 4012번: 컨벤션 센터 [C++]

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

문제

컨벤션 센터

풀이

young 님의 블로그를 참고했습니다.

$i$번째 단체의 시작 시간을 $s_i$, 끝 시간을 $e_i$라 합시다.

문제의 답은 $M$입니다.

구간 $(l, r)$에 포함되는 단체만 고려했을 때 컨벤션 센터를 사용할 수 있는 단체의 최댓값을 빠르게 구할 수 있다면, $1$번 단체가 사용하지 않은 나머지 구간을 $M - 1$개의 단체가 사용할 수 있는지 판단하여 $1$번 단체가 컨벤션 센터를 사용해도 되는지 판단할 수 있습니다.

마찬가지로 $2$번, $3$번, $\cdots$, $N$번 단체가 컨벤션 센터를 사용해도 되는지도 같은 방식으로 판단할 수 있습니다.

구간의 최댓값

열린 구간 $(l, r)$에 포함되는 단체만 고려했을 때 컨벤션 센터를 사용할 수 있는 단체의 최댓값을 빠르게 찾아봅시다.

입력으로 주어진 단체들을 시작 날짜를 기준으로 정렬해 줍니다. 이때 다른 구간을 포함하는 단체들은 좌우로 더 넓어 손해이므로 제거해 줍니다.

이분 탐색을 이용해서 $(l, r)$에 포함되는 단체 중 $e_i$가 가장 큰 것을 찾아줍시다. 다른 구간을 포함하는 구간은 모두 제거했으므로 이 단체의 $s_i$가 가장 크고, 따라서 이를 선택하는 것이 가장 이득입니다.

이제 이 단체와 구간이 겹치지 않으면서 왼쪽에 있는 단체를 찾아줍시다. 왼쪽에 있는 단체를 찾는 것을 계속 반복하면 답을 구할 수 있지만, 시간 복잡도가 $O(N)$이므로 희소 배열을 이용해서 최적화해 줍시다.

$st[i][0]$를 $s_i$보다 빨리 끝나면서 시작 시간이 가장 늦은 단체 번호라고 하고, $st[i][k] = st[st[i][k - 1]][k - 1]$로 정의해주면 됩니다.

이제 희소 배열을 이용해서 처음 이분 탐색으로 찾은 단체부터 $l$ 이후에 시작하는 첫 단체까지 단체의 개수를 세어줄 수 있습니다.

이러한 동작을 하는 함수를 $c(l, r)$이라 합시다.

단체 포함 판단

단체 $1$을 포함하게 되는 경우 구간은 $(0, s_1)$과 $(e_1, \infty)$로 나뉩니다.

따라서 $c(0, s_1) + c(e_1, \infty) = c(0, \infty) - 1$이라면 단체 $1$을 포함해도 됩니다.

단체를 포함하는 경우마다 매번 쪼개진 모든 구간을 확인할 수는 없으므로 맵과 이분 탐색을 이용해서 단체가 들어갈 수 있는 유일한 구간 하나를 찾읍시다.

해당 구간을 또 쪼개서 답이 바뀌지 않는지 테스트 하면 됩니다.

코드

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

#define all(v) (v).begin(), (v).end()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), (v).end())

#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define by_desc(x) [](const auto& a, const auto& b) { return a.x > b.x; }

constexpr int MX = 202020, INF = 2e9;

struct Range {
    int start, end, id;
};

int prevId[MX][20];

Range rng[MX], s[MX], e[MX];
vector<Range> stk;

int getMaxCntOfRange(int l, int r) {
    auto it = lower_bound(all(stk), Range(0, r, 0), by(end));
    if (it == stk.begin())
        return 0;

    auto [start, end, id] = *(it - 1);

    if (start <= l)
        return 0;

    int ret = 1;
    for (int i = 17; i >= 0; i--) {
        if (rng[prevId[id][i]].start <= l)
            continue;

        id = prevId[id][i];
        ret += 1 << i;
    }

    return ret;
}

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

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        auto& [start, end, id] = rng[i];
        id = i;
        cin >> start >> end;

        s[i] = e[i] = rng[i];
    }
    sort(s + 1, s + 1 + N, by(start));
    sort(e + 1, e + 1 + N, by(end));

    for (int i = 1, j = 1, prev = 0; i <= N; i++) {
        auto& [start, end, id] = s[i];

        while (not stk.empty() and end <= stk.back().end)
            stk.pop_back();
        stk.push_back(s[i]);

        for (; e[j].end < start; j++) {
            if (rng[prev].start < e[j].start)
                prev = e[j].id;
        }
        prevId[id][0] = prev;

        for (int k = 1; k < 18; k++)
            prevId[id][k] = prevId[prevId[id][k - 1]][k - 1];
    }

    println("{}", getMaxCntOfRange(0, INF));

    map<int, int> endOfStart;
    endOfStart[0] = 0;
    endOfStart[INF] = INF;

    for (int id = 1; id <= N; id++) {
        auto& [start, end, _] = rng[id];

        auto l = endOfStart.upper_bound(start);
        auto r = l--;

        if (start <= l->second or r->first <= end)
            continue;

        if (getMaxCntOfRange(l->second, start) +
                getMaxCntOfRange(end, r->first) ==
            getMaxCntOfRange(l->second, r->first) - 1) {
            print("{} ", id);
            endOfStart.emplace(start, end);
        }
    }

    return 0;
}

백준 4012번: 컨벤션 센터 [C++]