Attention:

At the beginning, [0, 1000000000)is white,and the second test's output is [..., 1000000000), and in fact you have to deal it with[0, 1000000000 - 1), or you'll got wa. I don't know why!


Forgive my english:)

Edited by author 13.11.2011 16:28

I saw your solution run at 0.046s, it was really fast. however I use segmentTree to get accept at 0.64s. what kind of algorithm do you use?

I don't know what you have been doing, but the bruteforce is 0.156s which is 4.4 times faster than your idea. What I'm trying to say is that you dont need segmentTrees for this problem, unless you want to exercize on them; the naive approach is also very fast :)