백준 2517 달리기 혼내주기

 

 

 

머지소트트리로 풀었는데, 좌표를 압축해서 그냥 세그로 풀면 메모리를 훨씬 줄일 수 있어서 다시 풀었다.
능력의 범위는 10억까지지만 총 갯수는 500000이므로 좌표 압축을 하고 각각이 leaf인 세그를 만든다. 이후 들어온 사람 순서대로 [0,자신의능력) 구간에 몇명이나 있는지 쿼리를 날리고 매번 해당 사람을 update 해주면 된다.

엄청난 메모리 & 시간 차이

 

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

const int N = 1<<19;
vector<pii> arr;
int tree[N<<1];
int n;

void input() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int num; cin >> num;
        arr.push_back({num, i+1});
    }
}

void update(int l, int r, int i = 1, int s = 0, int e = N-1) {
    if(l > e || r < s) return ;
    if(l <= s && e <= r) {
        tree[i] = 1;
        return ;
    }
    int m = (s + e) >> 1;
    update(l, r, i<<1, s, m);
    update(l, r, i<<1|1, m+1, e);
    tree[i] = tree[i<<1] + tree[i<<1|1];
}

int query(int l, int r, int i = 1, int s = 0, int e = N-1) {
    if(l > e || r < s) return 0;
    if(l <= s && e <= r) return tree[i];
    int m = (s + e) >> 1;
    return query(l, r, i<<1, s, m) + query(l, r, i<<1|1, m+1, e);
}

bool cmp(pii& a, pii& b) {
    return a.second < b.second;
}

int main() {
    fastio;
    input();

    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
    
    for(int i = 0; i < n; ++i) {
        arr[i].first = i;
    }

    sort(all(arr), cmp);
    
    for(auto& v : arr) {
        cout << v.second - query(0, v.first-1) << "\n";
        update(v.first, v.first);
    }
}