BOJ 17131 여우가 정보섬에 올라온 이유

1 개요

BOJ 17131 여우가 정보섬에 올라온 이유

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

2 C++

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

struct Star {
    int x, y;
};

class Tree {
public:
    vector<int> node;

    void Insert(int cur, int left, int right, int index, int val) {
        if (left == right) {
            node[cur] += val;
            return;
        }
        int mid = (left + right) / 2;
        if (index <= mid) Insert(cur * 2, left, mid, index, val);
        else Insert(cur * 2 + 1, mid + 1, right, index, val);
        node[cur] = node[cur * 2] + node[cur * 2 + 1];
    }

    long Search(int cur, int left, int right, int start, int end) {
        if (left > end || right < start) return 0;
        if (left <= start && right >= end) return node[cur];
        int mid = (start + end) / 2;

        long sum = 0;
        if (left <= mid) sum += Search(cur * 2, left, right, start, mid);
        if (right > mid) sum += Search(cur * 2 + 1, left, right, mid + 1, end);
        return sum;
    }
};

#define MOD 1000000007
int N;
Tree t;
vector<Star> stars;
vector<int> batch_y;

long calculateBatch() {
    long ret = 0;
    for (auto itr = batch_y.begin(); itr != batch_y.end(); itr++) {
        ret = (ret + t.Search(1, 0, *itr - 1, 0, N - 1) * t.Search(1, *itr + 1, N - 1, 0, N - 1)) % MOD;
    }
    for (auto itr = batch_y.begin(); itr != batch_y.end(); itr++) {
        t.Insert(1, 0, N - 1, *itr, 1);
    }
    return ret;
}

void solve() {
    sort(stars.begin(), stars.end(), [](const Star& a, const Star& b) {
        return a.x < b.x;
    });

    int prev = MOD;
    int rank = -1;
    for (int i = 0; i < N; i++) {
        if (prev != stars[i].x) rank++;
        prev = stars[i].x;
        stars[i].x = rank;
    }

    sort(stars.begin(), stars.end(), [](const Star& a, const Star& b) {
        return a.y > b.y;
    });
    t.node.resize(4 * N);

    long answer = 0;
    int past_y = MOD;
    for (int i = 0; i < N; i++) {
        if (past_y != stars[i].y) {
            answer = (answer + calculateBatch()) % MOD;
            batch_y.clear();
            past_y = stars[i].y;
        }
        batch_y.push_back(stars[i].x);
    }
    answer = (answer + calculateBatch()) % MOD;
    cout << answer;
}

int main() {
    cin >> N;
    stars.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> stars[i].x >> stars[i].y;
    }
    solve();
}