Pagini recente » Cod sursa (job #2101152) | Cod sursa (job #849025) | Cod sursa (job #1921383) | Cod sursa (job #2174188) | Cod sursa (job #1774809)
#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;
}