Cod sursa(job #2104951)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 ianuarie 2018 14:01:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <vector>

using namespace std;

class Segm_Tree {
public:
  
  Segm_Tree () {

    cin >> n;
    sol.resize (n + 1);
    val.resize (n + 1);
    tree.resize (n << 2);

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

    Init(1, n, 1);
  }

  void Solve () {
    for (int i = n; i >= 1; -- i) {
      Update (val[i], i, 1, n, 1);
    }

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

private:
  
  int n;
  vector < short int > tree, val, sol;

  void Init (int st, int dr, int cur_node) {
    if (st == dr) {
      tree[cur_node] = 1;
      return;
    }
  
    int mid = (st + dr) >> 1;
    int left = cur_node << 1;
    int right = left | 1;

    Init (st, mid, left);
    Init (mid + 1, dr, right);

    tree[cur_node] = tree[left] + tree[right];
  }

  void Update (int poz, int who, int st, int dr, int cur_node) {
    if (st == dr) {
      sol[st] = who;
      tree[cur_node] = 0;
      return;
    }
  
    int mid = (st + dr) >> 1;
    int left = cur_node << 1;
    int right = left | 1;
    
    if (tree[left] >= poz) {
      Update (poz, who, st, mid, left);
    }
    else {
      Update (poz - tree[left], who, mid + 1, dr, right);
    }

    tree[cur_node] = tree[left] + tree[right];
  }
};

int main () {

  ios::sync_with_stdio(false);

  freopen ("schi.in", "r", stdin); 
  //FISIERE !!
  freopen ("schi.out", "w", stdout);
  
  Segm_Tree T;
  T.Solve();
}