Cod sursa(job #3189099)

Utilizator PescarusTanislav Luca Andrei Pescarus Data 4 ianuarie 2024 14:50:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
using namespace std;
const int nmax = 30005;
int arbi[4 * nmax], v[nmax];
int sol[nmax];


void build(int nod, int st, int dr){
  if(st == dr){
    arbi[nod] = 1;
    return;
  }
  int mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);
  arbi[nod] = arbi[2 * nod] + arbi[2 * nod + 1];
}


int query(int nod, int st, int dr, int x){
  if(st == dr){
    return st;
  }
  int mid = (st + dr) / 2;
  if(x <= arbi[2 * nod]){
    return query(2 * nod, st, mid, x);
  }
  else{
    return query(2 * nod + 1, mid + 1, dr, x - arbi[2 * nod]);
  }
}

void update(int nod, int st, int dr, int x){
  if(st == dr){
    arbi[nod] = 0;
    return;
  }
  int mid = (st + dr) / 2;
  if(x <= mid){
    update(2 * nod, st, mid, x);
  }
  else{
    update(2 * nod + 1, mid + 1, dr, x);
  }
  arbi[nod] = arbi[2 * nod] + arbi[2 * nod + 1];
}


int main(){
  ifstream f("schi.in");
  ofstream g("schi.out");
  int n;
  f >> n;
  for(int i = 1; i <= n; i++){
    f >> v[i];
  }
  build(1, 1, n);
  for(int i = n; i >= 1; i--){
    int poz = query(1, 1, n, v[i]);
    sol[poz] = i;
    update(1, 1, n, poz);
  }
  for(int i = 1; i <= n; i++){
    g << sol[i] << '\n';
  }
  
  return 0;
}