Cod sursa(job #954056)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 28 mai 2013 08:47:03
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>

#define In "schi.in"
#define Out "schi.out"
#define Size 160000
#define Nmax 30002
#define Left_Son() 2*node
#define Right_Son() 2*node+1

using namespace std;

class SegmentTree
{
    public :
    inline void Update(int node,int left,int right,int pos,int value)
    {
        if(left == right)
            a[node] = value;
        else
        {
            int middle = (left + right) >> 1;
            if(pos<=middle)
                Update(Left_Son(),left,middle,pos,value);
            else
                Update(Right_Son(),middle+1,right,pos,value);
            a[node] = a[Left_Son()] + a[Right_Son()];

        }
    }
    inline int Query(int node,int left,int right,int value)
    {
        if(left == right)
            return left;
        int middle = (left + right) >> 1;
        if(value<=a[Left_Son()])
            return Query(Left_Son(),left,middle,value);
        return Query(Right_Son(),middle+1,right,value - a[Left_Son()]);
    }
    private : int a[Size];
};
SegmentTree A;

int main()
{
    int N , i, pos;
    int a[Nmax],rez[Nmax];
    ifstream f(In);
    f >> N;
    for( i = 1 ;i <= N; ++i )
    {
        f>>a[i];
        A.Update(1, 1, N, i, 1);
    }
    f.close();
    for(i = N  ; i ; --i)
    {
        pos = A.Query(1, 1, N, a[i]);
        rez[pos] = i;
        A.Update(1, 1, N, pos, 0);
    }
    ofstream g(Out);
    for(i = 1 ; i <= N ; ++i)
        g<<rez[i]<<"\n";
    g.close();
    return 0;
}