Cod sursa(job #1603534)

Utilizator LucianTLucian Trepteanu LucianT Data 17 februarie 2016 17:17:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#define maxN 30005
using namespace std;
int arb[maxN*4];
int loc[maxN*4];
int sol[maxN*4];
int n, i, j, pos;
void build(int nod, int st, int dr)
{
    int mij;
    if(st == dr)
    {
        arb[nod]=1;
        return;
    }
    mij=(st+dr)/2;
    if(pos <= mij) build(2*nod, st, mij);
    else build(2*nod+1, mij+1, dr);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}
void update(int nod, int st, int dr, int poz)
{
    int mij;
    if(st == dr)
    {
        arb[nod]=0;
        sol[st]=pos;
        return;
    }
    mij=(st+dr)/2;
    if(poz <= arb[2*nod])
        update(2*nod, st, mij, poz);
    else update(2*nod+1, mij+1, dr, poz-arb[2*nod]);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}
int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        pos=i;
        build(1, 1, n);
    }
    for(i = 1; i <= n; i++)
        scanf("%d", &loc[i]);
    for(i = n; i >= 1; i--)
    {
        pos=i;
        update(1, 1, n, loc[i]);
    }
    for(i = 1; i <= n; i++)
        printf("%d\n", sol[i]);
    return 0;
}