Cod sursa(job #2048306)

Utilizator LauraNaduLaura Nadu LauraNadu Data 25 octombrie 2017 22:03:51
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n, i, a[30003], aib[30003], sol[30002];
void update1(int p)
{
    for(;p<=n;p+=(p & -p))
        aib[p]++;
}
void update2(int p)
{
    for(;p<=n;p+=(p & -p))
        aib[p]--;
}
int query(int p)
{
    int r=0;
    for(;p;p-=(p & -p))
        r+=aib[p];
    return r;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
        update1(i);
    }
    for(i=n;i;i--)
    {
        int st=1;
        int dr=n;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            a[0]=query(mij);
            if(a[0]<a[i])
                st=mij+1;
            else dr=mij-1;
        }
        sol[st]=i;
        update2(a[i]);
    }
    for(i=1;i<=n;i++)
        g<<sol[i]<<"\n";
    return 0;
}