Cod sursa(job #1519657)

Utilizator andreiudilaUdila Andrei andreiudila Data 7 noiembrie 2015 17:55:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;

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

int n,i,aux, poz,val,x,y;
int v[30005], sol[30005];
int aint[120010];
int suma;

void update(int nod, int l, int r)
{
    if(l==r) aint[nod] = val;
    else
    {
        int mid=(l+r)/2;

        if(poz<=mid) update(2*nod, l, mid);
        else update(2*nod+1, mid+1, r);

        aint[nod]=aint[2*nod] + aint[2*nod+1];
    }

}

void query(int nod, int l, int r)
{
    if(l>=x && r<=y )  suma+=aint[nod];
    else
        {
            int mid=(l+r)/2;

            if(x<=mid) query(2*nod, l, mid);
            if(y>mid) query(2*nod+1, mid+1, r);
        }
}

int cauta_x(int v)
{
    int l=1,r=n,mid;

    while(l<=r)
    {
        mid=(l+r)/2;
        suma=0;
        x=1; y=mid;

        query(1, 1, n);

        if(suma<v) l=mid+1;
        else r=mid-1;
    }

    return l;
}


int main()
{
    fin>>n;

    for(i=1;i<=n;i++){
        fin>>v[i];
        poz=i;
        val=1;
        update(1, 1, n);
    }

    for(i=n;i>=1;i--)
    {

     poz=cauta_x(v[i]);

     sol[poz]=i;

     val=0;
     update(1, 1, n);
    }

    for(i=1;i<=n;i++) fout<<sol[i]<<"\n";

    return 0;
}