BOJ 5419 : 북서풍

5419번: 북서풍 (acmicpc.net)

 

좌표 압축 + 세그먼트 트리 + 스위핑으로 풀 수 있는 문제이다.

 

만약 i번째 점이 좌표 (xi, yi)에 있다고 하자. 그렇다면, i번째 점으로 항해할 수 있는 점들은 yi보다 y좌표가 높고, xi보다 x좌표가 낮은 점들의 집합인 것이 자명하다. 여기서 xi보다 x좌표가 낮은 점들은 스위핑을 하며 자동적으로 구해지고, yi보다 y좌표가 높은 점들은 세그먼트 트리로 구할 수 있다.

 

우리는 X 좌표순으로 오름차순 정렬, 같다면 Y 좌표로 내림차순 정렬하면 스위핑을 할 수 있는 상황이 만들어진다. 정렬 순서대로 쭉 훑어나가면, i번째 좌표 기준으로 갱신된 점의 좌표는 xi보다 왼쪽에 있는 점들밖에 갱신이 안 되었기 때문에, 그저 yi보다 높은 좌표를 가진 점들만 구하면 되며, 이때 세그먼트 트리를 사용할 수 있는 조건이 만들어진다.

 

그런데 보면, yi의 범위는 20억이다. (-10^9 ~ 10^9.) 20억개의 원소를 가지는 배열을 만들 수는 없으므로, 이때 좌표 압축이 들어간다. 이상이다.

 

번외로, 이 문제는 굉장히 시간 범위가 타이트하다. cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0) 과 같은 전처리를 하지 않으면 시간 초과가 날 수 있으니, 유의한다. 실제로 전처리 안해서 TLE 받았다. 이에 대해 문의는 넣어놓은 상태이다.

 

난이도(개인적): Platinum IV

난이도(객관적): Platinum IV

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define pp pair<int, pair<int, int> >

int N, R[75001];
vector<pp> pos;
int tree[4 * 75001];

int query(int node, int start, int end, int left, int right) {
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;
    int l = query(node * 2, start, mid, left, right);
    int r = query(node * 2 + 1, mid + 1, end, left, right);
    return l + r;
}

void update(int node, int left, int right, int idx, int val) {
    if (left > idx || right < idx) return;
    if (left == right) {
        tree[node] = val;
    }
    else {
        int mid = (left + right) / 2;
        update(node * 2, left, mid, idx, val);
        update(node * 2 + 1, mid + 1, right, idx, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

void update(int idx, int val) {
    R[idx] = val;
    update(1, 0, N - 1, idx, val);
}

bool cmpy(pp left, pp right) {
    return left.second.second < right.second.second;
}

bool cmpx(pp left, pp right) {
    if (left.second.first == right.second.first) return left.second.second > right.second.second;
    return left.second.first < right.second.first;
}

void solve() {

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 4; j++) {
            tree[i * 4 + j] = 0;
        }
        R[i] = 0;
    }

    pos.clear();

    for (int i = 0; i < N; i++) {
        int x, y; cin >> x >> y;
        pos.push_back({ i, {x, y} });
    }

    sort(pos.begin(), pos.end(), cmpy);

    int r = -2000000007; int ptr = -1;

    for (int i = 0; i < N; i++) {
        int t = pos[i].second.second;
        int idx = pos[i].first;
        if (t != r) { ptr++; r = t; }
        pos[i].second.second = ptr;
    }

    sort(pos.begin(), pos.end(), cmpx);

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        int idx = pos[i].first;
        int t = pos[i].second.second;
        ans += query(1, 0, N - 1, t, N - 1);
        update(t, R[t] + 1);
    }

    cout << ans << endl;

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T; while (T--) {
        solve();
    }
}