Best Position on the Road
Time limit: 1 s.
Memory limit: 256 MB
A road is represented by the integer number line.
The kingdom receives a sequence of requests. Each request adds a new closed segment \([l, r]\) on the road. These segments represent restricted zones.
After each new segment is added, you must choose an integer position \(x\) on the road.
The distance between a point \(x\) and a segment \([l, r]\) is defined as:
\(\mathrm{dist}(x, [l, r]) = \begin{cases} 0 & \text{if } l \le x \le r \\ l - x & \text{if } x \lt l \\ x - r & \text{if } x \gt r \end{cases}\)
In words, the distance is \(0\) if the point lies inside the segment, otherwise it is the distance to the nearest endpoint.
For a fixed point \(x\), define its score as the maximum distance from \(x\) to any segment that has been added so far.
Your task is to choose the integer \(x\) that minimizes this score after each update. If there are multiple optimal choices, output the smallest one.
Input
The first line contains one integer \(Q\). \((1 \le Q \le 2 \cdot 10^5)\)
Each of the next \(Q\) lines contains two integers \(l_i\) and \(r_i\). \((1 \le l_i \le r_i \le 10^9)\)
Output
For each query, output one integer — the best position after processing that query.
Scoring
| Group | Constraints | Points |
|---|---|---|
| \(1\) | \(l_i = 1\) | \(23\) |
| \(2\) | \(Q, l_i, r_i \le 200\) | \(25\) |
| \(3\) | \(l_i = r_i\) | \(32\) |
| \(4\) | — | \(20\) |
Examples
Input
4
3 5
7 9
2 4
5 9
Output
3
6
5
5
Input
3
1 4
1 1
1 2
Output
1
1
1
Note
In the First Example:
After 1st update: \((3,5)\) becomes \([3,5]\)
Intervals: \([3,5]\)
We choose a point \(x\) minimizing the maximum distance to \([3,5]\).
- Any point inside \([3,5]\) has distance \(0\) to the interval.
- The best choice is \(x = 3\) (smallest optimal point).
Answer: \(3\)
After 2nd update: \((7,9)\) becomes intervals \([3,5], [7,9]\)
We now choose \(x\) minimizing the maximum distance to both intervals.
- The best point is between them.
- Checking candidates, \(x = 6\) balances distance to both intervals.
Answer: \(6\)
After 3rd update: \((2,4)\) becomes intervals \([2,4], [3,5], [7,9]\)
Now intervals are closer on the left.
- The optimal point shifts left.
- Best choice becomes \(x = 5\).
Answer: \(5\)
After 4th update: \((5,9)\) becomes intervals \([2,4], [3,5], [5,9], [7,9]\)
Now intervals heavily overlap on the right.
- The best position remains \(x = 5\).
Answer: \(5\)
Solution
Only two endpoints matter:
- \(L\), the maximum left endpoint;
- \(R\), the minimum right endpoint.
If \(L\le R\), every point in \([L,R]\) belongs to every segment, so the smallest optimal position is \(L\).
Otherwise, the score is \(\max(L-x,x-R)\). It is minimized at the middle of \(R\) and \(L\); when there are two optimal integers, integer division selects the smaller one.
Maintain \(L\) and \(R\) after every update. The complexity is \(O(Q)\) time and \(O(1)\) memory.
#include <algorithm>
#include <iostream>
#include <limits>
using namespace std;
int main() {
int q;
cin >> q;
long long maximumLeft = numeric_limits<long long>::min();
long long minimumRight = numeric_limits<long long>::max();
while (q--) {
long long left, right;
cin >> left >> right;
maximumLeft = max(maximumLeft, left);
minimumRight = min(minimumRight, right);
if (maximumLeft <= minimumRight) {
cout << maximumLeft << '\n';
} else {
cout << (maximumLeft + minimumRight) / 2 << '\n';
}
}
}