달리기

백준 2517번: 달리기

아이디어

자기보다 실력 높은사람 몇명 있는지 구하면 된다. 그런데 실력의 최댓값이 10억이다. 사이즈 10억짜리 배열을 만들면 터지니까 좌표 압축을 해야한다. N은 최대 50만이니까 충분히 가능하다. 좌표 압축은 map으로 했다. 실력순으로 정렬 후 제일 작은 값부터 순서대로 0, 1, 2….

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 500001;
int N;
vector<int> arr, v;
vector<int> tree(MAX*4);
map<int, int> m;

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];
}

int 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 >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
        v.push_back(x);
    }

    sort(arr.begin(), arr.end());
    for (int i = 0; i < N; i++) {
        m[arr[i]] = i;
    }

    for (int i = 0; i < N; i++) {
        cout << query(0, N-1, m[v[i]], N-1, 1)+1 << '\n';
        update(0, N-1, m[v[i]], 1);
    }
    return 0;
}

여담

간당간당하게 통과했다. 다른사람들 푼거 보니까 pair<int, int>로 하나는 실력, 하나는 압축된 좌표 이런식으로 써서 시간복잡도를 줄였다. 나중에 시간제한 걸리면 저렇게 해야겠다.