I usually use segment trees or interval trees to update on a given intrerval say [ 1 , N ] and need maximum 2^K memory where 2^K>2*N-1, but in this case the interval in which we would want updates is too big 10^9 and that's a definetely NO for a segment tree with 2^30 nodes!!!
So can you please give me some hints on how to solve this in O(n*logn) with or without using a segment tree, please :)

First do the separate ,then the memoty will be just 2*2*N.
Remember there are just 10000 numbers.
sorry for my poor English.

I got AC in 0.015s
My solution is O(n*logn)
I just use a Heap.