Задача из второго тура SNWS-10. Про медиану. Дано N (1<=N<=10^6) чисел. Числа добавляются в изначально пустой набор в заданном порядке. Требуется определять медиану после каждого добавления числа. 

Я реализовал бинарное дерево поиска по Кормену. Однако получил TL на 11 тесте. Вот код:

struct binary_elem {
long key,size,left,right;
};

vector<binary_elem> BT;

binary_elem BT_init(long key) {
binary_elem res;
res.key=key;
res.size=1;
res.left=-1;
res.right=-1;
return res;
}

void BT_insert (binary_elem z) {
long y=-1,x=0;
BT.push_back(z);
long cur=BT.size()-1;
if (cur==0) return;
while (x!=-1) {
y=x;
BT[x].size++;
if (z.key<BT[x].key) x=BT[x].left; else x=BT[x].right;
}
if (y!=-1)
if (z.key<BT[y].key) BT[y].left=cur; else BT[y].right=cur;
}

long BT_select (long x, long i) {
long r;
while (true) {
if (BT[x].left==-1) r=1; else r=BT[BT[x].left].size+1;
if (i==r) return BT[x].key;
else if (i<r) { x=BT[x].left; } else {x=BT[x].right; i=i-r; }
}
}

int main(){
long n,num,i;
freopen("median.in","rt",stdin);
freopen("median.out","wt",stdout);
scanf("%d",&n);
for (i=0;i<n;i++) {
scanf("%d",&num);
BT_insert(BT_init(num));
long res = BT_select(0,(i+2)/2);
printf("%d ",res);
}
}

Подскажите плз, что не так. Или как ее можно решить по-другому. Я посмотрел, некоторые ее решили за 5-7 минут!