Cod sursa(job #2137110)

Utilizator GoogalAbabei Daniel Googal Data 20 februarie 2018 16:52:04
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 3 * 1e4;

int n;
int aint[1 + 4 * NMAX];
int a[1 + NMAX];
int res[1 + NMAX];

void compute_tree(int node, int le, int ri) {
  if(le == ri)
    aint[node] = 1;
  else {
    int mid = (le + ri) / 2;
    compute_tree(2 * node, le, mid);
    compute_tree(2 * node + 1, mid + 1, ri);

    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
}

void update(int node, int pos, int le, int ri, int ind) {
  if(le == ri) {
    res[le] = ind;
    aint[node] = 0;
  } else {
    int mid = (le + ri) / 2;
    if(aint[2 * node] >= pos)
      update(2 * node, pos, le, mid, ind);
    else
      update(2 * node + 1, pos - aint[2 * node], mid + 1, ri, ind);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> a[i];

  compute_tree(1, 1, n);

  for(int i = n; i >= 1; i--)
    update(1, a[i], 1, n, i);

  for(int i = 1; i <= n; i++)
    out << res[i] << ' ';

  in.close();
  out.close();
  return 0;
}