Cod sursa(job #1597742)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 12 februarie 2016 11:51:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

using VS = vector<short>;

int n, poz;
VS a, q, v;

inline void Solve(int i);
int BS(int k);
inline void Build(int nod, int st, int dr);
inline void Update(int nod, int st, int dr, int poz);
inline int Sum(int nod, int st, int dr, int poz);

int main()
{
    is >> n;
    a = VS(4 * n + 1);
    q = v = VS(n + 1);
    Build(1, 1, n);
    for ( int i = 1; i <= n; ++i )
        is >> v[i];
    int poz;
    for ( int i = n; i; --i )
    {
        poz = BS(v[i]);
        q[poz] = i;
        Update(1, 1, n, poz);
    }
    for ( int i = 1; i <= n; ++i )
        os << q[i] << "\n";
    is.close();
    os.close();
    return 0;
}

int BS(int k)
{
    int st = 1, dr = n, md, s;
    while ( st <= dr )
    {
        md = ( st + dr ) / 2;
        s = Sum(1, 1, n, md);
        if ( k <= s )
            if ( k == s && !q[md] )
                return md;
            else
                dr = md - 1;
        else
            st = md + 1;
    }
    return md;
}

inline int Sum(int nod, int st, int dr, int poz)
{
    if ( st == dr )
        return a[nod];
    int md = ( st + dr ) / 2;
    if ( poz <= md )
        return Sum(2 * nod, st, md, poz);
    else
        return a[2 * nod] + Sum(2 * nod + 1, md + 1, dr, poz);
}

inline void Build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        a[nod] = 1;
        return;
    }
    int md = ( st + dr ) / 2;
    Build(2 * nod, st, md);
    Build(2 * nod + 1, md + 1, dr);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}

inline void Update(int nod, int st, int dr, int poz)
{
    if ( st == dr )
    {
        a[nod] = 0;
        return;
    }
    int md = ( st + dr ) / 2;
    if ( poz <= md )
        Update(2 * nod, st, md, poz);
    else
        Update(2 * nod + 1, md + 1, dr, poz);
    a[nod] = a[2 * nod] + a[2 * nod + 1];
}