Cod sursa(job #1673066)

Utilizator BrandonChris Luntraru Brandon Data 3 aprilie 2016 13:54:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <cmath>

using namespace std;

const int MaxN = (1 << 15);

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

int qry[MaxN], SegTree[2 * MaxN], place[MaxN];
int n, RgLim;

inline int LfSon(const int &node) {
  return node * 2;
}

inline int RgSon(const int &node) {
  return node * 2 + 1;
}

inline void LimInit() {
  RgLim = log2(n);
  RgLim += ((1 << RgLim) < n);
  RgLim = (1 << RgLim);
}

void BuildTree(int l = 1, int r = RgLim, int node = 1) {
  if(l == r) {
    SegTree[node] = 1;
    return;
  }

  int med = (l + r) / 2;

  BuildTree(l, med, LfSon(node));
  BuildTree(med + 1, r, RgSon(node));

  SegTree[node] = SegTree[LfSon(node)] + SegTree[RgSon(node)];
}

void Update(int pos, int l = 1, int r = RgLim, int node = 1) {
  if(l == r) {
    SegTree[node] = 0;
    return;
  }

  int med = (l + r) / 2;

  if(pos <= med) {
    Update(pos, l, med, LfSon(node));
  }
  else {
    Update(pos, med + 1, r, RgSon(node));
  }

  SegTree[node] = SegTree[LfSon(node)] + SegTree[RgSon(node)];
}

int Query(int val, int l = 1, int r = RgLim, int node = 1) {
  if(l == r) {
    return l;
  }

  int med = (l + r) / 2;
  int ans = -1;

  if(val <= SegTree[LfSon(node)]) {
    ans = Query(val, l, med, LfSon(node));
  }
  else {
    ans = Query(val - SegTree[LfSon(node)], med + 1, r, RgSon(node));
  }

  return ans;
}

int main() {
  cin >> n;

  for(int i = 1; i <= n; ++i) {
    cin >> qry[i];
  }

  LimInit();
  BuildTree();

  for(int i = n; i >= 1; --i) {
    int qry_ans = Query(qry[i]);
    Update(qry_ans);
    place[qry_ans] = i;
  }

  for(int i = 1; i <= n; ++i) {
    cout << place[i] << '\n';
  }

  return 0;
}