Cod sursa(job #1825637)

Utilizator d0rina2011Craciun Dorina d0rina2011 Data 9 decembrie 2016 15:34:21
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int n, v[30001], aib[120001], sol[30001], p, a;

void build (int node, int left, int right)
{
    if(left == right)
        aib[node] = 1;
    else
    {
        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
        aib[node] = aib[2 * node] + aib[2 * node + 1];
    }
}
void update (int node, int left, int right, int x)
{
    if(right == left)
        aib[node] = 0;
    else
    {
        int mid = (left + right)/2;
        if(mid >= x)
            update(2 * node, left, mid, x);
        else
            update(2 * node + 1, mid + 1, right, x);
        aib[node] = aib[2 * node] + aib[2 * node + 1];
    }
}
void query (int node, int left, int right, int x)
{
    if(left == right)
        p = left;
    else
    {
        int mid = (left + right) / 2;
        if(x <= aib[2 * node])
            query(2 * node, left, mid, x);
        else
            query(2 * node + 1, mid + 1, right, x - aib[2 * node]);
    }
}

int main()
{
    int i;
    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>v[i];
    }
    build(1, 1, n);
    for(i = n; i >= 1; --i){
        a = v[i];
        p = 0;
        query(1, 1, n, a);
        sol[p] = i;
        update(1, 1, n, p);
    }
    for(i = 1; i <= n; ++i)
        fout<<sol[i]<<" ";
    return 0;
}