BOJ 5419 북서풍

개요

BOJ 5419 북서풍

• 백준 온라인 저지 5419번 문제
• BOJ 46단계

C++

#include <bits/stdc++.h>
using namespace std;

#define ll long long
struct Island {
    int x, y;
};
vector<Island> islands;
vector<int> yarr;

class SegTree {
public:
    vector<ll> tree;
    int n;

    SegTree(int N) : n(N) {
        tree.resize(4 * n, 0);
    }

    void update(int idx, int val) {
        updateUtil(1, 0, n - 1, idx, val);
    }

    ll query(int l, int r) {
        return queryUtil(1, 0, n - 1, l, r);
    }

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

    ll queryUtil(int node, int start, int end, int l, int r) {
        if (r < start || l > end) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return queryUtil(2 * node, start, mid, l, r) + queryUtil(2 * node + 1, mid + 1, end, l, r);
    }
};

void solve() {
    sort(yarr.begin(), yarr.end());
    yarr.erase(unique(yarr.begin(), yarr.end()), yarr.end());

    for (auto &i : islands) {
        i.y = lower_bound(yarr.begin(), yarr.end(), i.y) - yarr.begin();
    }

    sort(islands.begin(), islands.end(), [](const Island &a, const Island &b) {
        return a.x < b.x || (a.x == b.x && a.y > b.y);
    });

    SegTree st(yarr.size());
    ll sum = 0;

    for (auto &i : islands) {
        sum += st.query(i.y, yarr.size() - 1);
        st.update(i.y, 1);
    }
    cout << sum << endl;
}

void sub() {
    int N;
    cin >> N;
    islands.clear();
    yarr.clear();
    islands.resize(N);
    yarr.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> islands[i].x >> islands[i].y;
        yarr[i] = islands[i].y;
    }
    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        sub();
    }
}