It was uneasy, but I did it! 3 days of thinking left. I use array of ranges. Each range is both-direction (parent-child) tree. I crossed the input 3 times (for read data, for evaluate a length of each subnode, for build array of ranges.
I had such problems, such as TLE (I solved it with refusing of lists, I use child array[10^5] for each node). I get MLE-Memory limit exception (It solved with evaluate of node length O(n). it was hard!).
The tree was a genious idea! But I had TLE, becouse I ran from 0 to ChildArr.Length everytime. I need in dynamically an BeginChildId for each parent. TLE went away from my eyes!
4 cycle has Mx(crossing the ranges) complexity. I used a PrevOtr object. 1 query could to have 1 or 2 ranges (begin of 2 range, so keep in mind! You must understand that).
That is part of FindNode function  code:
...
do
            {
                prv = null;
                for (int i = inner.BegChild; i < inner.ChildN//inner.Childs.Count()
                    ; i++)
                    if (query >= inner.Childs[i].X && query <= inner.Childs[i].Y)
                    {
                        prv = inner.Childs[i];
                            inner.BegChild = i;
                        break;
                    }
                if (prv != null)
                    inner = prv;
            }
            while (prv != null);
...

Edited by author 15.10.2018 17:15

From all suggested hints, this is the fastest way to do it.
Initially I tried with trees, but I was getting TLE on #13.
Finally I decided to use a map for the points (with key=point, value=index)
It's a very convenient Data Structure, because it provides fast search for the nearest value (lower bound), and allows you to delete that point once its segment has been found.
I tried without deleting it, but got TLE #14.
Deleting each point from the map after finding it makes the map smaller after each iteration.

Finally got an AC in 0.1

Try to use 'longint' instead of 'int64'. In some problems it helps if you have WA.

thanks

Thank you so much for the test!

Stack can be used in place of set, reducing time to about 0.148 sec

Edited by author 29.05.2017 14:16

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

My code passes this test... Still getting WA5.

The following test helped me to get AC:
7
2 8
2 6
3 3
6 6
7 7
8 8
9 10
10
1
2
3
4
5
6
7
8
9
10
Answer:
-1
2
3
2
2
4
5
6
7
7
I used points sorting + stack approach. My error was in sorting function: I didn't handle situation when points have the same coordinates, the same types, but belong to different segments. Once I added condition which deals with segment numbers, I got AC.
By the way, different compilers may give different results: my program compiled with visual studio gave correct results, while g++ did not.

Edited by author 05.01.2020 20:01

Your sample is incorrect. Because in the statment:
"The segments are ordered by non-decreasing ai, and when ai = aj they are ordered by decreasing length. All segments are distinct."

1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point.
Any idea for modifications?

That's OK. In this problem you may output numbers with any whitespaces between them. If all the numbers are right, your solution will be accepted.

There's o(n+m) solution.

Yes