I solved the following problem http://acm.timus.ru/problem.aspx?space=1&num=2055 using approach described here http://codeforces.com/blog/entry/15296 + binary search, but my solution barely fits in Time Limit.

There are solutions 10 times faster than mine and I'm very interested what approach could they be using?