Cod sursa(job #2622259)

Utilizator ddeliaioanaaDumitrescu Delia Ioana ddeliaioanaa Data 31 mai 2020 19:34:22
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>
std::ifstream fin("schi.in");
std::ofstream fout("schi.out");

const int N = 30001;
int n, tree[4 * N], v[N], res[N];


// ne trb un arbore care sa reprezinte vectorul plin de 1 la incep(n-am dat niciun loc)
void build(int node, int left, int right)
{
    if(left == right)
    {
        tree[node] = 1;
        return;
    }
    int mid = (left + right) / 2;
    build(node * 2, left, mid);
    build(node * 2 + 1, mid + 1, right);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

//ne trebuie o functie de update pe care sa o apelam pt a da un loc si a-l marca cu 0
void update(int node, int left, int right, int index, int val) //
{
    if(left == right)
    {
        tree[node] = 0;
        res[right] = val;
        return;
    }
    int mid = (left + right) / 2;

    if(tree[node * 2] >= index) //daca in subarborele stg am mai multi de 1 decat pozitia pe care vreau sa o dau ma duc acolo
        update(node * 2 , left, mid, index, val);
    else      //altfel ma duc in subraborele drept si tin cont ca in stanga am deja tree[node * 2] de 1
        update(node * 2 + 1, mid + 1, right, index - tree[node * 2], val);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];

}


int main()
{
    int i;
    fin >> n;
    for(i = 0; i < n; i++)
        fin >> v[i];
    build(1, 0, n - 1);

    for(i = n - 1; i >= 0; i--)
        update(1, 0, n - 1, v[i], i + 1);

    for(i = 0; i < n; i++)
        fout << res[i] << '\n';




    return 0;
}