Cod sursa(job #3259825)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 27 noiembrie 2024 22:40:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>

#define MAXN 30001

struct SegmentTree{
  private:
  int aint[4*MAXN];
  int n;
  void update(int node, int s, int d, int pos){
    if(s==d && s==pos){
      aint[node] = 0 ;
    }
    else{
      int m = (s+d)/2;
      if(pos<=m)
        update(node*2, s, m, pos);
      else
        update(node*2+1, m+1, d, pos);
      aint[node] = aint[node*2] + aint[node*2+1];
    }
  }

  int query(int node, int s, int d, int val){
    if(s==d){
      return s;
    }
    else{
      int m = (s+d)/2;
      if(val<=aint[2*node])
        return query(node*2, s, m, val);
      else
        return query(node*2+1, m+1, d, val-aint[2*node]);
    }
  }
  void build(int node, int s, int d){
    if(s==d){
      aint[node] = 1;
    }
    else{
      build(node*2, s, (s+d)/2);
      build(node*2+1, (s+d)/2+1, d);
      aint[node] = aint[node*2] + aint[2*node+1];
    }
  }
  public:
  void update(int pos){
    update(1, 0, n-1, pos);
  }
  int query(int val){
    return query(1, 0, n-1, val);
  }
  void init(int n){
    this->n = n;
    build(1, 0, n-1);
  }
};

int n;
SegmentTree aint;
int v[MAXN];
int pos[MAXN];

int main(){
  FILE *fin, *fout;
  fin = fopen("schi.in", "r");
  fout = fopen("schi.out", "w");
  fscanf(fin, "%d", &n);
  aint.init(n);
  for(int i=0; i<n; i++)
    fscanf(fin, "%d", &v[i]);

  for(int i=n-1; i>=0; i--){
    int smaller = aint.query(v[i]);
    aint.update(smaller);
    pos[smaller] = i;
  }
  for(int i=0; i<n; i++)
    fprintf(fout, "%d\n", pos[i]+1);
  fclose(fin);
  fclose(fout);
  return 0;
}