One of the solutions would involve sorting and stacks. I've tried to use reb-black tree, but it seems to have problems with dublicate-keys.

Edited by author 14.08.2015 22:05

I got AC by iterating all the ranges and putting them in a stack. Basically, if next range fits into previous one, put it in a stack. If it does not, remove previous ranges from the stack until it does (or the stack gets empty).
At each step, update the answers to relevant queries. Binary search is good enough for finding them.

it's possible to solve this problem with segment tree. Just put all answers into segment tree with meaning -1 and then update it with segments, sorted by range