Cod sursa(job #1854194)

Utilizator MithrilBratu Andrei Mithril Data 22 ianuarie 2017 14:53:32
Problema Schi Scor 100
Compilator cpp Status done
Runda gym_emag_avansati_2016 Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 30005;
ifstream fin("schi.in");
ofstream fout("schi.out");
int initPos[NMAX],arb[4*NMAX],finalPos[NMAX],pos;

void update(int n,int low,int high,int pos,int val)
{
    int m=(low+high)>>1,leftN=n<<1,rightN=leftN|1;

    if(low==high)
    {
        arb[n]=val;
        return;
    }
    if(pos<=m)
        update(leftN,low,m,pos,val);
    else
        update(rightN,m+1,high,pos,val);

    arb[n]=arb[leftN]+arb[rightN];
}

void query(int n,int low,int high,int val)
{
    int m=(low+high)>>1,leftN=n<<1,rightN=leftN|1;

    if(low==high)
    {
        pos=low;
        return;
    }

    if(val<=arb[leftN])
        query(leftN,low,m,val);
    else
        query(rightN,m+1,high,val-arb[leftN]);
}

int main()
{
    int n,i,j;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>initPos[i];
        update(1,1,n,i,1);
    }
    for(i=n;i>0;i--)
    {
        query(1,1,n,initPos[i]);
        finalPos[pos]=i;
        update(1,1,n,pos,0);
    }
    for(i=1;i<=n;i++)
        fout<<finalPos[i]<<"\n";
}