Cod sursa(job #2470063)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 8 octombrie 2019 17:47:00
Problema Schi Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>

using namespace std;

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

const int NMAX = 30000;
int v[NMAX + 1];
int sol[NMAX + 1];
int aint[NMAX * 4 + 1];
int s;

void build( int nod, int st, int dr ){
  int med;
  if( st == dr ){
    aint[nod] = v[st];
    return;
  }
  med = (st + dr) >> 1;
  build( 2 * nod, st, med );
  build( 2 * nod + 1, med + 1, dr );
  aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void query( int nod, int st, int dr, int a, int b ){
  int med;
  if( a <= st && dr <= b ){
    s += aint[nod];
    return;
  }
  med = (st + dr) >> 1;
  if( a <= med )
    query( (nod << 1), st, med, a, b );
  if( b > med )
    query( (nod << 1) | 1, med + 1, dr, a, b );
}

void update( int nod, int st, int dr, int a, int val ){
  int med;
  if( st == dr ){
    aint[nod] = val;
    return;
  }
  med = (st + dr) >> 1;
  if( a <= med )
    update( (nod << 1), st, med, a, val );
  else
    update( (nod << 1) | 1, med + 1, dr, a, val );
  aint[nod] = aint[nod << 1] + aint[(nod << 1) | 1];
}

int main() {
    int n, i;
    fin >> n;
    for( i = 1; i <= n; ++i )
      v[i] = 1;
    build( 1, 1, n );
    for( i = 1; i <= n; ++i )
      fin >> v[i];
    for( i = n; i >= 1; --i ){
      int st, dr, med;
      st = 0;
      dr = n;
      while( dr - st > 1 ){
        med = (st + dr) >> 1;
        s = 0;
        query(1, 1, n, 1, med);
        if( s < v[i] )
          st = med;
        else
          dr = med;
      }
      sol[dr] = i;
      update( 1, 1, n, dr, 0 );
    }
    for( i = 1; i <= n; ++i )
      fout << sol[i] << "\n";
    return 0;
}