Cod sursa(job #2944211)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 22 noiembrie 2022 10:43:38
Problema Schi Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

int const NMAX = 30000;
int arr[1 + NMAX];
int ski[1 + NMAX];

struct SegmentTree {
  vector <int> seg;
  SegmentTree(int n = 0) {
    seg.resize(4 * n);
  }

  void update(int node, int from, int to, int pos, int x) {
    if(from == to){
      seg[node] = 1;
    }else {
      int mid = (from + to) / 2;
      if(pos <= mid) {
        update(node * 2, from, mid, pos, x);
      }else {
        update(node * 2 + 1, mid+1, to, pos, x);
      }
      seg[node] = seg[node * 2] + seg[node * 2 + 1];
    }
  }

  int query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return seg[node];
    }else {
      int mid = (from + to) / 2, ans = 0;
      if(x <= mid) {
        ans += query(node * 2, from, mid, x, min(mid, y));
      }
      if(mid < y) {
        ans += query(node * 2 + 1, mid+1, to, max(x, mid+1), y);
      }
      return ans;
    }
  }
};

int main() {

  int n;
  in >> n;
  for(int i = 1;i <= n;i++) {
    in >> arr[i];
  }
  SegmentTree seg(n);
  for(int i = n;i >= 1;i--) {
    int add = seg.query(1, 1, n, 1, arr[i]), removed;
    removed = add;
    //cout << "/\n";
    while(add != 0) {
      arr[i] = arr[i] + add;
      add = seg.query(1, 1, n, 1, arr[i]) - removed;
      removed += add;
    }
    //cerr << arr[i] << ' ' << add << ' ' << add + arr[i] << '\n';
    ski[arr[i]] = i;
    seg.update(1, 1, n, arr[i], 1);
  }
  //cerr << '\n';
  for(int i = 1;i <= n;i++) {
    out << ski[i] << '\n';
  }
  return 0;
}