@admin @taran_1407 Could you please reply to the queries? It is not appreciated. It seems not good idea to ignore messages after the contest is over. Lot of people like me facing problem for this problem but no body cares to look into that. It demotivates the coder.
Try to visualize the movement of right pointer. Assume for now that intervals in second block are in sorted order (r_i < r_j). Now for the queries in the first block, the right pointer can go up to N. If the intervals in the second block are also in sorted order, then for the first query in the second block, the right pointer has to move again to the beginning (ie, the smallest possible right pointer for the second block), and again process queries up to N in the worst case.
But instead, we can do better if we sort the intervals in the second block in decreasing order of right pointers. In this case, the right pointer doesn’t have to go all the way to the leftmost interval and come back up to the rightmost one. This time as the intervals are reverse-sorted, so we start processing the queries in reverse order and travel to the leftmost interval, but we don’t have to return back to the rightmost point as the queries are already processes (which we were doing in the previous case).
For the third block, the queries are again in sorted order, and we were at the leftmost point of the second block, and so again the right pointer has to travel comparatively less distance.
Hope it helps.
4 Likes
Thanks. Its clear now.
@dvyn01 Can you help me to find the problem in above solution? I get TLE for subtask 3. What I am doing wrong?
Nice explanation !