PROBLEM LINK:
Author: Lalit Kundu
Editorialist: Animesh Fatehpuria
DIFFICULTY:
Medium
PREREQUISITES:
Segment Tree
PROBLEM:
Given a sequence P of N pairs of integers and Q queries of the form (a , b) : For each query find an index i in P[] such that P[i].first \ge a , P[i].second \ge b and P[i].first  a + P[i].second  b is minimised. If there exists multiple options print the one which minimises i. If no such indices exist, print 1.
N,Q \le 10^5.
P[i],a,b \le 10^9.
QUICK EXPLANATION:
======================
We process the queries offline. We store all the Q queries in a list and sort the list in descending order of “a” value. Similarly, we sort the array P[] in descending order of P[i].first. We process the queries in the defined order and maintain a segment tree which considers all the indices such that. P[i].first \ge a. Whenever we process a query (a,b), we would have already updated all the indices whose P[i].first \ge a in the segment tree. Now just do a range minimum query for the range [b,10^9] to look for the index which minimises P[i].first + P[i].second.
EXPLANATION:
================
Let us first observe the function we are trying to minimise.
For each query, we need to minimise P[i].first  a + P[i].second  b, and also follow the constraints mentioned on P[i].
It is easy to notice that a,b are constant for each query, so we can rewrite the function as (P[i].first + P[i].second)  ( a + b ).
Now we can see that we just have to minimise P[i].first + P[i].second.
Observe that there are no updates on P. We can use this to reorder the queries in a way which makes our job easier.
According to the question, we must consider only those indices i such that P[i].first \ge a and P[i].second \ge b, and then
try to minimise their sum. Let’s try to get rid of P[i].first \ge a. We can do this by sorting the queries in descending order
of a and sorting the array P[] in descending order of P[i].first. We process the queries in this changed order and maintain
a segment tree. Whenever we process a query (a,b), we would have already updated all the indices whose P[i].first \ge a in the segment tree.
I’ll describe how to implement the segment tree in the next paragraph.
Assume we have done this successfully. Our task now is to find an index i such that P[i].second \ge b and out of all the options that we have, we need to choose the one which minimises P[i].first + P[i].second. In case of ties, we need to pick the one with the lowest index.
We can manage this by implementing a segment tree ordered by P[i].second in which each node( corresponding to [L,R] ) stores the following things:

The best index in that range.

sum = P[index].first + P[index].second.
How will we merge two nodes? The answer to this question lies simply in the function we want to minimise. Our first priority is to minimise P[index].first + P[index].second. After that, we need to try to minimise index. Therefore, our merge function will look something like this:
// Merges left child and right child
node merge( node left , node right ):
if( left.sum < right.sum )
return left;
else if( right.sum < left.sum )
return right;
else: // Minimise index
if( left.index < right.index )
return left;
return right;
The answer to each query is now the best index in the range [b,10^9].
We need to handle one more thing. The values can be as large as 10^9, so we can’t implement a segment tree naively. We have two choices here:

Compress the values to cover a smaller range i.e [1,N].

Implement an Implicit Segment Tree.
Either of these ways would suffice and pass easily within the time limits. The complexity of this solution would be \mathcal{O}(N\log{}N) or \mathcal{O}(N\log{}10^9) depending on which way you prefer.
For implementation and clarity, see setter’s and editorialist’s commented code.