Boj 2517 c++ 달리기

https://www.acmicpc.net/problem/2517

 

 

문제

달리기 선수들이 트랙에 있는 순서대로 선수들이 실력이 주어진다. 각 선수는 자기보다 실력이 낮은 선수를 추월할 수 있다. 자기보다 높은 실력의 선수는 추월할 수 없다. 이때, 각 선수들의 최대 등수를 출력하시오.

 

입력으로는 선수의 수 N이 주어지고 다음 N줄에는 각 선수들의 실력이 주어진다.

 

제한

 

1<= N <= 500000

각 선수들의 실력 1이상 10억 이하

 

 

접근 & 풀이 

 

각 선수들의 실력을 세그먼트 트리에 추가했을 당시에 자기 자신을 포함하여 자신보다 실력이 뛰어난 선수의 수를 구하면 된다.

이는 각 선수의 실력을 인덱스로 하는 세그먼트 트리에 각 입력마다 1을 추가하여 구간합을 구하는 방식으로 해결할 수 있다. 

하지만 문제는 실력의 제한이 10억이기 때문에 트리를 생성하기에는 메모리초과가 발생할 위험이 있다.

때문에, 각 선수들의 실력의 대소관계만 판별할 수 있도록 좌표압축을 해준 후 구간 쿼리를 구현해주면 정답을 받을 수 있다.

 

 

정답코드

 

#include <bits/stdc++.h>
#define int long long
#define MAX 500001
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

vector<int> tree, arr;

void add(int curr, int s, int e, int idx) {
    if(idx < s || idx > e)return;
    if(s == e) {tree[curr] += 1; return;}
    int mid = (s+e)/2;
    add(curr*2, s, mid, idx);
    add(curr*2+1, mid+1, e, idx);
    tree[curr] = tree[curr*2] + tree[curr*2+1];
}

int f(int curr, int s, int e, int l, int r) {
    if(r < s || l > e)return 0;
    if(l <= s && e <= r)return tree[curr];

    int mid = (s+e)/2, rsum, lsum;
    lsum = f(curr*2, s, mid, l, r);
    rsum = f(curr*2+1, mid+1, e, l, r);
    return lsum + rsum;
}

int32_t main() {

    fastio

    int N; cin >> N;

    arr.resize(N);
    tree.resize(4*MAX, 0);
    vector<int> number(N);

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

    map<int, int> cmpnum;

    for(int i = 0; i < N; i++) {
        cmpnum[number[i]] = i;
    }

    for(int i = 0; i < N; i++) {
        arr[i] = cmpnum[arr[i]];
    }

    for(int i = 0; i < N; i++) {
        add(1, 0, MAX, arr[i]);
        cout << f(1, 0, MAX, arr[i], MAX) << "\n";
    }
}