Cod sursa(job #2337881)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 6 februarie 2019 19:29:38
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
 
#define MAXN 30000
#define INF 1000000
 
using namespace std;
 
ifstream fin( "schi.in" );
ofstream fout( "schi.out" );

struct Node
{
  int v, t;
};

Node aint[4*MAXN+5];
int lazy[4*MAXN+5];

void build( int p, int val, int poz, int st, int dr )
{
  if( p<st || dr<p )
    return;
    
  if( st==dr )
    aint[poz]=Node{val,p};
  else
  {
    int mid=(st+dr)/2;
    
    build(p,val,2*poz,st,mid);
    build(p,val,2*poz+1,mid+1,dr);
    
    if( aint[2*poz].v<aint[2*poz+1].v )
      aint[poz]=aint[2*poz];
    else
      aint[poz]=aint[2*poz+1];
  }
}

void propagate( int poz, int st, int dr )
{
  aint[poz].v+=lazy[poz];

  if( st!=dr )
  {
    lazy[2*poz]+=lazy[poz];
    lazy[2*poz+1]+=lazy[poz];
  }
  
  lazy[poz]=0;
}

void update( int a, int b, int val, int poz, int st, int dr )
{ 
  if( b<st || dr<a )
    return;
    
  propagate(poz,st,dr);  

  if( a<=st && dr<=b )
  {
    lazy[poz]+=val;
    propagate(poz,st,dr);
  }
  else
  {
    int mid=(st+dr)/2;
    
    update(a,b,val,2*poz,st,mid);
    update(a,b,val,2*poz+1,mid+1,dr);
    
    if( aint[2*poz].v<aint[2*poz+1].v )
      aint[poz]=aint[2*poz];
    else
      aint[poz]=aint[2*poz+1];
  }
}

int main( )
{
  int n;
  
  fin>>n;
  
  for( int i=1;i<=n;i++ )
    build(i,INF,1,1,n);
  
  for( int i=1;i<=n;i++ )
  {
    int k;
    
    fin>>k;
    
    build(i,k,1,1,n);
  }
  
  //in aint[1].t am pozitia celui mai din dreapta 1

  for( int i=1;i<=n;i++ )
  {
    int j=aint[1].t;
    
    build(j,INF,1,1,n);
    
    if( j<n )
      update(j+1,n,-1,1,1,n);
      
    fout<<j<<'\n';
  }
  
	return 0;
}