Cod sursa(job #1628301)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 3 martie 2016 22:47:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

int a[150000], n, v[30005], sol[30005], nr, prim, ultim, poz;

ifstream f("schi.in");
ofstream g("schi.out");

void Caut(int nod, int st, int dr)
{   if (prim<=st && dr<=ultim)
    {   ultim+=a[nod];
        nr+=a[nod];
    }
    else
    {   int m=(st+dr)/2;
        if (prim<=m)
            Caut(2*nod, st, m);
        if (m<ultim)
            Caut(2*nod+1, m+1, dr);
    }
}

void Modific(int nod, int st, int dr)
{   if (st==dr)
        a[nod]++;
    else
    {   int m=(st+dr)/2;
        if (poz<=m)
            Modific(2*nod, st, m);
        else
            Modific(2*nod+1, m+1, dr);
        a[nod]=a[2*nod]+a[2*nod+1];
    }
}

int main()
{   int i;
    f>>n;
    for (i=1; i<=n; ++i)
        f>>v[i];
    for (i=n; i; --i)
    {   nr=0;
        prim=1;
        ultim=v[i];
        Caut(1, 1, n);
        sol[v[i]+nr]=i;
        poz=v[i]+nr;
        Modific(1, 1, n);
    }
    for (i=1; i<=n; ++i)
        g<<sol[i]<<'\n';
    return 0;
}