백준 5419번: 북서풍

Seungil Kim·2021년 12월 11일
0

PS

목록 보기
133/206

북서풍

백준 5419번: 북서풍

아이디어

자기보다 x좌표가 크면서 y좌표가 작은 점이 몇개인지 세면 된다.
x좌표 오름차순으로 정렬해서 순서대로 자기보다 y좌표가 작은 애가 몇개나 있는지 보면 하나도 빼놓지 않고 찾을 수 있다.
y좌표가 작은 애가 몇개인지 찾기 위해 좌표압축을 하고, 세그트리의 리프에 해당 y좌표에 점이 존재하는지를 기록한다. 쿼리를 0부터 현재 y좌표까지 날리면 자기보다 x좌표가 크면서 y좌표가 작은 점의 개수를 알려준다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 75000;
int T, N;
vector<int> arr, tree;

void update(int start, int end, int idx, int node) {
    if (idx < start || end < idx) return;
    if (start == end) {
        tree[node]++;
        return;
    }
    update(start, (start+end)/2, idx, node*2);
    update((start+end)/2+1, end, idx, node*2+1);
    tree[node] = tree[node*2] + tree[node*2+1];
}

long long query(int start, int end, int left, int right, int node) {
    if (end < left || right < start) return 0;
    if (left <= start && end <= right) return tree[node];
    return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        vector<int> sorted;
        vector<pair<int, int>> coords;
        map<int, int> ycoord;
        cin >> N;
        arr = vector<int>(N, 0);
        tree = vector<int>(4*N, 0);
        for (int i = 0; i < N; i++) {
            int x, y;
            cin >> x >> y;
            coords.push_back({-x, y});
            sorted.push_back(y);
        }
        sort(coords.begin(), coords.end());
        sort(sorted.begin(), sorted.end());
        for (int i = 0; i < N; i++) {
            ycoord[sorted[i]] = i;
        }
        long long ans = 0;
        for (auto p : coords) {
            ans += query(0, N-1, 0, ycoord[p.second], 1);
            update(0, N-1, ycoord[p.second], 1);
        }
        cout << ans << '\n';
    }
    return 0;
}

여담

간당간당하게 통과! 저번에 풀었던 공장이랑 비슷한 문제다.

profile
블로그 옮겼어용 https://ks1ksi.io/

2개의 댓글

comment-user-thumbnail
2021년 12월 11일

승일님 전역하시면 저 ps 과외 좀 해주세요.

1개의 답글