Cod sursa(job #2528560)

Utilizator RedXtreme45Catalin RedXtreme45 Data 22 ianuarie 2020 09:41:26
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#define Nmax 30001
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,v[Nmax],aib[Nmax],sol[Nmax];
int query(int poz1)
{
    int S=0;
    for (int i=poz1;i>0;i-=(i&(-i)))
    {
        S+=aib[i];
    }
    return S;
}
void update(int poz1)
{
    for (int i=poz1;i<=n;i+=(i&(-i)))
    {
        aib[i]++;
    }
}
int main()
{
    int i;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    for (i=n;i>0;i--)
    {
        int x=v[i];
        int d=0;
        while (query(x)>d)
        {
            x+=query(x);
            d=query(x);
        }
        int poz=query(x);
        int x1=v[i]+poz;
        if (sol[x1]==0)
        sol[x1]=i;
        else
        {
            while (sol[x1]!=0)
                x1--;
                sol[x1]=i;
        }

        update(v[i]);
    }
    for (i=1;i<=n;i++)
        fout<<sol[i]<<"\n";
    return 0;
}