I know that this problem could be solved using sorting and something like that - my friends do so but don't share code, I don't know how.
I used brute force (= the easiest way) and i got AC 0.281    330 KB at C++

You can use structure Heap or Interval Tree ( because the value of the elements is rather small ).
Heap : O(NlogM)
Interval tree : O(N log(Max_Value) ).
Interval tree also can give you the k-th smallest value in log (Max_value).

And I've wrote it with maximizator in O(m*log(n)).

You can read about this and many other structures in this lecture: http://zorg-n-ko.nm.ru/lecture.html

My solution is O(N).

Yes... and with little bit of optimization, one can get AC in half of that time... :)

Edited by author 20.03.2016 19:06