백준 5480번: 전함 [C++]

작성일 | In
플래티넘 II 플래티넘 II

문제

전함

풀이

레이저로 전함을 부수는 것은 다르게 생각하면 전함이 레이저에 맞아 부서지는 것으로 생각할 수 있습니다. 전함이 어떤 레이저에 의해서 부서졌는지는 전함을 지나가는 레이저 중 인덱스가 가장 작은 것을 구하면 알 수 있습니다.

수평 레이저와 수직 레이저를 분리해서 생각하면 각 레이저를 하나의 정수로 나타낼 수 있으므로 레이저와 인덱스를 매핑하여 세그먼트 트리를 이용하면 최솟값을 빠르게 구할 수 있습니다.

각 축에 따라 레이저 좌표를 압축한 뒤 전함이 포함하고 있는 레이저의 구간을 구해서 해당 구간의 레이저의 인덱스의 최솟값을 구해 해당 레이저가 부순 가장 큰 무게를 업데이트 해 주면 됩니다.

테스트 케이스당 시간 복잡도는 $\mathcal{O}(k\log l)$입니다.

코드

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = INT_MAX;

struct SegmentTree {
    int n;
    vector<int> t;

    SegmentTree(int _n): n(_n), t(n << 1, INF) {}

    void minimize(int i, int v) {
        i += n;
        for (t[i] = min(t[i], v); i > 1; i >>= 1)
            t[i >> 1] = min(t[i], t[i ^ 1]);
    }

    int getRangeMin(int l, int r) {
        int ret = INF;

        if (l > r)
            return ret;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1)
                ret = min(ret, t[l++]);
            if (~r & 1)
                ret = min(ret, t[r--]);
        }

        return ret;
    }
};

vector<int> verVec, horVec;
void compress(vector<int>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
int lower_bound(vector<int>& v, int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}
int upper_bound(vector<int>& v, int x) {
    return upper_bound(v.begin(), v.end(), x) - v.begin();
}

struct Battleship {
    pair<int, int> x, y;
    int weight;

    Battleship() = default;

    Battleship(int x1, int y1, int x2, int y2, int w):
    x(x1, x2), y(y1, y2), weight(w) {
        if (x.first > x.second)
            swap(x.first, x.second);
        if (y.first > y.second)
            swap(y.first, y.second);
    }
} ships[101010];

pair<int, int> cannons[101010];

void solve() {
    verVec.clear();
    horVec.clear();

    int n, k, l;
    cin >> n >> k >> l;

    for (int i = 1; i <= k; i++) {
        int x, y, xx, yy, w;
        cin >> x >> y >> xx >> yy >> w;
        ships[i] = Battleship(x, y, xx, yy, w);
    }

    for (int i = 1; i <= l; i++) {
        int a, b;
        cin >> a >> b;

        cannons[i] = pair(a, b);
        if (b)
            verVec.push_back(a);
        else
            horVec.push_back(a);
    }

    compress(verVec), compress(horVec);
    SegmentTree verSeg(verVec.size()), horSeg(horVec.size());

    for (int i = 1; i <= l; i++) {
        auto [a, b] = cannons[i];

        if (b)
            verSeg.minimize(lower_bound(verVec, a), i);
        else
            horSeg.minimize(lower_bound(horVec, a), i);
    }

    vector<int> ans(l + 1);
    for (int i = 1; i <= k; i++) {
        int idx = verSeg.getRangeMin(
            lower_bound(verVec, ships[i].x.first),
            upper_bound(verVec, ships[i].x.second) - 1
        );

        idx = min(idx, horSeg.getRangeMin(
            lower_bound(horVec, ships[i].y.first),
            upper_bound(horVec, ships[i].y.second) - 1
        ));

        if (idx != INF)
            ans[idx] = max(ans[idx], ships[i].weight);
    }

    for (int i = 1; i <= l; i++)
        cout << ans[i] << '\n';
}

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

    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}

백준 5480번: 전함 [C++]