Cod sursa(job #2017668)

Utilizator savigunFeleaga Dragos-George savigun Data 1 septembrie 2017 23:42:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int MAX = 3e4 + 1;

class Segmenet_Tree {
public:
  Segmenet_Tree(int n) {
    this -> n = n;
    arb.resize((MAX << 2));
  }

  void update(int target, int val) {
    _update(target, val, 1, this -> n, 1);
  }

  int query(int target) {
    return _query(target, 1, this -> n, 1);
  }

private:
  int n;
  vector < short int > arb;

  void _update(int target, int val, int st, int dr, int nod) {
    if (st == dr) {
      arb[nod] = val;
      return;
    }

    int middle = (st + dr) >> 1;

    if (target <= middle) {
      _update(target, val, st, middle, nod << 1);
    }
    else {
      _update(target, val, middle + 1, dr, nod << 1 | 1);
    }

    arb[nod] = arb[nod << 1] + arb[nod << 1 | 1];
  }

  int _query(int val, int st, int dr, int nod) {
    if (st == dr) {
      return st;
    }

    int middle = st + dr >> 1;

    if (arb[nod << 1] >= val) {
      return _query(val, st, middle, nod << 1);
    }

    return _query(val - arb[nod << 1], middle + 1, dr, nod << 1 | 1);
  }
};

int main(int argc, char const *argv[]) {

  int n;
  cin >> n;

  Segmenet_Tree *T = new Segmenet_Tree(n);
  vector < short int > v (MAX);

  for (int i = 1; i <= n; i ++) {
    cin >> v[i];
    T -> update(i, 1);
  }

  vector < short int > sol (MAX);
  for (int i = n; i >= 1; i --) {
    int poz = T -> query(v[i]);
    sol[poz] = i;
    T -> update(poz, 0);
  }

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

  delete T;
}