All submissions for this problem are available.
Chef has recently discovered the method to crack the password verification system on a network of servers, and wants your help. Chef discovered that the servers have their Unique Identification Number (UIN) and to crack the password, he needs the median of those UIN’s.
The problem arises when he realizes that while he is trying to crack the password, new servers are being added to the network.
Can you help chef identify the median whenever he queries for it?
NOTE: For an sorted array A,A ... A[N]
If N is odd :: Median = ((N/2)+1)th element.
If N is even :: Median = Mean of (N/2)th and ((N/2)+1)th element.
Input will be the queries. The queries are of three types:
“ADD X” which adds a server with UIN ‘X’ to the network.
“MEDIAN” which gives the median.
“END” is the end of input file.
Outputs median of all the UIN’s in server at that instant whenever “MEDIAN” is queried.
It is guaranteed that the number of queries will never exceed 2*105.
WARNING: Use Fast I/O methods as input file is large.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.