BOJ)5480 전함

문제: icpc.me/5480

각 레이저가 파괴하는 전함의 무게의 최댓값을 출력하는 문제이다.

우리는 우선 쿼리를 전부 받아 오프라인으로 문제를 풀어볼거다.

일단 x좌표와 y좌표가 10억까지들어올수 있기 때문에 전함과 레이저의 x,y좌표를 모두 받아 각각 좌표압축 해준다.

이후 우리는 x와 y에 대한 세그먼트트리를 각각 생성하여 세그먼트 트리에 레이저의 인덱스의 최솟값을 저장할 것이다.

수직인 레이저는 x세그먼트 트리에 수평인 레이저는 y세그먼트 트리에 레이저의 인덱스를 해당 좌표에 최솟값 업데이트 시켜주면 된다.

이후 전함마다 각각 x,y세그트리에서 최솟값인 인덱스를 받는다 가장 작은 인덱스가 의미하는건 결국 그 전함을 파괴하는 레이저라고 보면 된다.

해당 레이저에 전함의 무게를 최댓값으로 업데이트 시켜준 후 쿼리 처리가 다 끝나면 결과를 순서대로 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_K 100000
#define INF 1100000000
using namespace std;
int t, n, k, l, xseg[12 * MAX_K], yseg[12 * MAX_K], res[MAX_K];
struct laser {
    int x, y;
};
struct ship {
    int x1, y1, x2, y2, m;
};
laser lsr[MAX_K];
ship sp[MAX_K];
vector<int> xpos;
vector<int> ypos;
int update(int *seg, int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = min(update(seg, pos, val, node * 2, x, mid), update(seg, pos, val, node * 2 + 1, mid + 1, y));
}
int query(int *seg, int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return INF;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return min(query(seg, lo, hi, node * 2, x, mid), query(seg, lo, hi, node * 2 + 1, mid + 1, y));
}
int get_xpos(int val) {
    return lower_bound(xpos.begin(), xpos.end(), val) - xpos.begin();
}
int get_ypos(int val) {
    return lower_bound(ypos.begin(), ypos.end(), val) - ypos.begin();
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(xseg, 0, sizeof(xseg));
        memset(yseg, 0, sizeof(yseg));
        memset(res, 0, sizeof(res));
        xpos.clear();
        ypos.clear();
        scanf("%d%d%d", &n, &k, &l);
        for (int i = 0; i < k; i++) {
            int a, b, c, d, e;
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
            xpos.push_back(a);
            xpos.push_back(c);
            ypos.push_back(b);
            ypos.push_back(d);
            sp[i] = { min(a,c),min(b,d),max(a,c),max(b,d),e };
        }
        for (int i = 0; i < l; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            if (b)
                xpos.push_back(a);
            else
                ypos.push_back(a);
            lsr[i] = { a,b };
        }
        sort(xpos.begin(), xpos.end());
        sort(ypos.begin(), ypos.end());
        xpos.erase(unique(xpos.begin(), xpos.end()), xpos.end());
        ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
        const int MAX_X = xpos.size();
        const int MAX_Y = ypos.size();
        for (int i = 0; i < MAX_X; i++)
            update(xseg, i, INF, 1, 0, MAX_X - 1);
        for (int i = 0; i < MAX_Y; i++)
            update(yseg, i, INF, 1, 0, MAX_Y - 1);
        for (int i = l - 1; i >= 0; i--) {
            if (lsr[i].y)
                update(xseg, get_xpos(lsr[i].x), i, 1, 0, MAX_X - 1);
            else
                update(yseg, get_ypos(lsr[i].x), i, 1, 0, MAX_Y - 1);
        }
        for (int i = 0; i < k; i++) {
            int idx = min(query(xseg, get_xpos(sp[i].x1), get_xpos(sp[i].x2), 1, 0, MAX_X - 1), query(yseg, get_ypos(sp[i].y1), get_ypos(sp[i].y2), 1, 0, MAX_Y - 1));
            if (idx == INF)continue;
            res[idx] = max(res[idx], sp[i].m);
        }
        for (int i = 0; i < l; i++) {
            printf("%d\n", res[i]);
        }
    }
    return 0;
}