Cod sursa(job #1774809)

Utilizator akaprosAna Kapros akapros Data 9 octombrie 2016 14:44:42
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>
#define maxN 30002
#define getc(n)  (n -> pos = (!n -> el) + (n -> l != NULL ? n -> l -> pos : 0) + (n -> r != NULL ? n -> r -> pos : 0))
using namespace std;
int n, v[maxN];
struct T
{
    int key, pos, el;
    T *l, *r;
    T(int key)
    {
        this->key = key, l = r = NULL;
        pos = el = 0;
    }
} *R;
void insert(T* &n, int L, int R)
{
    if (R < L)  return ;
    int mid = (L + R) >> 1;
    n = new T(mid);
    insert(n -> l, L, mid - 1);
    insert(n -> r, mid + 1, R);
    getc(n);
}
void get_pos(T* &n, int pos, int el)
{
    if (pos <= (n -> l != NULL ? n -> l -> pos : 0))
        get_pos(n->l, pos, el);
    else
    {
        if ((n -> l != NULL ? n -> l -> pos : 0) + (!n -> el) == pos)
            n -> el = el;
        else
            get_pos(n -> r, pos - (n -> l != NULL ? n -> l -> pos : 0) - (!n -> el), el);
    }
    getc(n);
}

void read()
{
    int i;
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}
void solve()
{
    srand(unsigned(time(NULL)));
    R = NULL;
    insert(R, 0, n - 1);
    for (int i = n; i >= 1; -- i)
        get_pos(R, v[i], i);
}
void write(T* &n)
{
    if (n == NULL)
        return ;
    write(n -> l);
    printf("%d\n", n-> el);
    write(n -> r);
}
int main()
{
    read();
    solve();
    write(R);
    return 0;
}