870. The Median As It Arrives
Values arrive one at a time. After each one, print the median of everything that has arrived so far, to exactly one decimal place.
With an odd count the median is the middle value. With an even count it is the
average of the two middle values. Every line has one decimal place, so an exact
integer still prints as 3.0.
Problem #273 finds the median of a fixed array, which is a sort. This is
different because the answer is wanted after every arrival, and re-sorting each
time is O(n^2 log n) overall.
Two heaps hold it: a max-heap of the smaller half and a min-heap of the larger
half. The median is then at one or both of the tops. Keep the sizes within one
of each other, and every arrival costs O(log n).
Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ value ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers in arrival order.
Output
Print n lines, each the median after that value arrives, to exactly one decimal place.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.