RMID2 - Running Median Again
Danish has just solved the problem Running Median.
The first line of the problem says "You will be given some integers in non-decreasing order". The problem asks you to report and remove the median of the list every time it is queried.
Having solved this problem, Danish now begins to wonder how to solve the problem if the input is in any order (not necessarily non-decreasing order as mentioned above).
Can you help him?
Your task is to take as input a list of positive integers. Whenever -1 is given as input, you must output the median of the list, and remove it from the list. Take the smaller element as the median in case of even number of elements.
Input
The input contains several test caes.
The first line contains an integer t, the number of test cases.
Each test case has several lines, each containing an integer n (<=10^9) . If n is positive, add it to the list. n=-1 indicates a median query (there will be no median query if the list is empty). The test case is terminated by n=0.
In each test case, there will be upto 10^5 integers to be added to the list, and upto 10^5 median queries.
Output
For each median query as described above, print the median on a new line.
Example
Input: 1 9 10 2 5 1 18 -1 -1 4 3 -1 8 7 -1 0 Output: 5 9 3 7
hide comments
hitthewall:
2022-04-04 10:42:33
thanks trouper_08, got AC after replacing cin/cout to cstdio stuff. |
|
lovrot:
2021-11-17 16:27:06
easy AC with use of iterators in set<> (c++) |
|
trouper_08:
2021-08-12 08:18:05
cout/cin didn't work due to strict time limit. Use scanf/printf ! AC after many WA and one TLE |
|
Christoph Dürr:
2020-11-20 18:41:51
Limit is to strict for Python. |
|
bucky_25:
2020-06-05 20:56:26
using policy based data str in c++ makes easy AC |
|
black_shroud:
2020-06-03 16:09:34
used BIT here , but how to do it using heaps?? |
|
sarthak_19:
2020-06-03 09:46:42
Nice Problem use both max and min heap |
|
khacchung98:
2020-05-10 11:49:31
nlog(n) giving TLE @@, so difficult Last edit: 2020-05-10 11:59:20 |
|
vidhan_1234:
2020-04-24 15:46:41
TLE in java. |
|
ashishgh1997:
2020-03-18 16:06:15
Variational question to traditional "Median In A Stream". Nice Question |
Added by: | Akhilesh Anandh |
Date: | 2013-10-05 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | variation on RMID |