달리기

*세그 트리 사용 

 

 

#include <iostream> #include <vector> #include <algorithm> #define MAXX 500001 using namespace std; typedef long long ll; typedef pair<ll, int> li; typedef pair<int, int> ii; int n; int tree[MAXX]; li num[MAXX]; void update(int idx, int diff) { while(idx <= n) { tree[idx] += diff; idx += (idx & -idx); } } int sum(int idx) { int res = 0; while (idx > 0) { res += tree[idx]; idx -= (idx & -idx); } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { int tmp; cin >> tmp; num[i].first = tmp; num[i].second = i; update(i, 1); } sort(num+1, num+1+n); vector<ii> res; for (int i = 1; i <= n; i++) { //자신의 실력이 낮으면 자신보다 실력이 높지만 뒤에 있는 선수들을 1만큼 감소한다. res.push_back(ii(num[i].second, sum(num[i].second))); update(num[i].second, -1); } sort(res.begin(), res.end()); for (int i = 0; i < res.size(); i++) { cout << res[i].second << '\n'; } return 0; }