Mr. Moneybags is a very rich man. He has an assistant Mr. Perfect, who one day, got very mad, and shredded some of Mr. Moneybag’s $100 bills! Mr. Moneybags decided to punish Mr. Perfect.
Mr. Moneybags tells Mr. Perfect to stack his money into different piles.
He starts with N (1 <= N <= 1,000,000, N odd) empty stacks, numbered 1..N. Mr. Moneybags then gives him a sequence of K instructions (1 <= K <= 25,000), each of the form "A B", meaning that Mr. Perfect should add one new bill to the top of each stack in the range A to B, inclusive. For example, if Mr. Perfect is told "11 13", then he should add a bill to each of the stacks 11, 12, and 13.
After Mr. Perfect finishes stacking the money according to his instructions, Mr. Moneybags would like to know the median height of his N stacks -- that is, the height of the middle stack if the stacks were to be arranged in sorted order (N is odd, so this stack is unique). Please write an efficient program to help Mr. Perfect determine the answer to Mr. Moneybag’s question.
- Line 1: Two space-separated integers, N K.
- Lines 2..1+K: Each line contains one of Mr. Moneybag’s instructions in the form of two space-separated integers A B (1 <= A <= B <= N).
7 4 5 5 2 4 4 6 3 5
There are N=7 stacks, and Mr. Moneybags issues K=4 instructions. The first instruction is to add a bill to stack 5, the second is to add a bill to each stack from 2..4, etc.
- Line 1: The median height of a stack after Mr. Perfect completes the instructions.
The winner is the one with the "most efficient" algorithm. So, if someone posts an O(N) solution, then it will beat any O(N^2). If there is a tie, aka, two or more people who post an O(N) solution, for example, then whoever has is the shortest code (code-golfed) wins.
So, your purpose is to write a efficient algorithm, and to prevent possible ties with other people, try to code-golf it as well.
Another thing, the input is to be read from a file and the output must be written to a file.
EDIT Also, the solution must be returned under or equal to 2 seconds. If it is not, you will receive a T. A wrong answer is an X. Which means, if no one can get it under time, then the most efficient algorithm sigh score of T can win.
EDIT #2 Here are some more samples:
EDIT #3 Bonus: (subtract 100 chars from total)
Solve this under 2 seconds :)