5480번: Battleship

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


$O(t(k+l)\lg(k+l))$

세그먼트 트리를 이용해 각 전함마다 맞은 첫 레이저를 찾고
해당 레이저에 격추시킨 전함 무게의 최댓값을 갱신해준다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MX = 1e5;
int t, k, m, a[MX][5], b[MX][2], tx[MX * 12], ty[MX * 12];
void update(int *arr, int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    arr[h] = min(arr[h], x);
    if (l^r) update(arr, h * 2 + 1, l, (l + r) / 2, g, x), update(arr, h * 2 + 2, (l + r) / 2 + 1, r, g, x);
}
int query(int *arr, int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return m;
    if (gl <= l&&r <= gr) return arr[h];
    return min(query(arr, h * 2 + 1, l, (l + r) / 2, gl, gr), query(arr, h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int main() {
    for (scanf("%d", &t); t--;) {
        map<int, int> mpx, mpy;
        int szx = 0, szy = 0, res[MX] = {};
        scanf("%*d%d%d", &k, &m);
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 5; j++) scanf("%d", a[i] + j);
            mpx[a[i][0]] = mpx[a[i][2]] = mpy[a[i][1]] = mpy[a[i][3]] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d", b[i], b[i] + 1);
            b[i][1] ? mpx[b[i][0]] = 0 : mpy[b[i][0]] = 0;
        }
        for (auto &it : mpx) it.second = szx++;
        for (auto &it : mpy) it.second = szy++;
        fill(tx, tx + szx * 4, m);
        fill(ty, ty + szy * 4, m);
        for (int i = 0; i < m; i++)
            b[i][1] ? update(tx, 0, 0, szx - 1, mpx[b[i][0]], i) : update(ty, 0, 0, szy - 1, mpy[b[i][0]], i);
        for (int i = 0; i < k; i++) {
            int n = min(query(tx, 0, 0, szx - 1, mpx[min(a[i][0], a[i][2])], mpx[max(a[i][0], a[i][2])]),
                query(ty, 0, 0, szy - 1, mpy[min(a[i][1], a[i][3])], mpy[max(a[i][1], a[i][3])]));
            if (n < m) res[n] = max(res[n], a[i][4]);
        }
        for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    }
    return 0;
}