Cod sursa(job #1597737)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 12 februarie 2016 11:48:54
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 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;

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 = VS(n + 1);
    Build(1, 1, n);
    Solve(1);
    for ( int i = 1; i <= n; ++i )
        os << q[i] << "\n";
    is.close();
    os.close();
    return 0;
}

inline void Solve(int i)
{
    if ( i > n )
        return;
    int x, poz;
    is >> x;
    Solve(i + 1);//if ( i < n  ) return;
    poz = BS(x);
    q[poz] = i;
    Update(1, 1, n, poz);
}

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];
}