B - Range Point Distance
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 l,r,x (l \leq r) に対して,dist(l,r,x) を次のように定義します.
- x<l のとき: dist(l,r,x)=l-x
- l \leq x \leq r のとき: dist(l,r,x)=0
- r<x のとき: dist(l,r,x)=x-r
整数のペアが N 個与えられ,そのうち i 個目のペアは (L_i,R_i) です. k=1,2,\cdots,N のそれぞれについて,次の問題を解いてください.
- 整数 x を自由に選び,\max(dist(L_1,R_1,x),dist(L_2,R_2,x),\cdots,dist(L_k,R_k,x)) を計算する. この値としてあり得る最小値を求めよ.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
各 k=1,2,\cdots,N に対する答えを順番に出力せよ.
入力例 1
3 1 3 2 4 5 6
出力例 1
0 0 1
- k=1 のときは x=1 とすればよいです.
- k=2 のときは x=3 とすればよいです.
- k=3 のときは x=4 とすればよいです.
入力例 2
10 64 96 30 78 52 61 18 28 9 34 42 86 11 49 1 79 13 59 70 95
出力例 2
0 0 2 18 18 18 18 18 18 21
Score : 400 points
Problem Statement
For integers l, r, and x (l \leq r), let us define dist(l,r,x) as follows.
- If x<l: dist(l,r,x)=l-x
- If l \leq x \leq r: dist(l,r,x)=0
- If r<x: dist(l,r,x)=x-r
You are given N pairs of integers, the i-th of which is (L_i,R_i). For each k=1,2,\cdots,N, solve the following problem.
- Let us choose an integer x freely and compute \max(dist(L_1,R_1,x),dist(L_2,R_2,x),\cdots,dist(L_k,R_k,x)). Find the minimum possible value of this.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Print the answers for k=1,2,\cdots,N in this order.
Sample Input 1
3 1 3 2 4 5 6
Sample Output 1
0 0 1
- For k=1, an optimal choice is x=1.
- For k=2, an optimal choice is x=3.
- For k=3, an optimal choice is x=4.
Sample Input 2
10 64 96 30 78 52 61 18 28 9 34 42 86 11 49 1 79 13 59 70 95
Sample Output 2
0 0 2 18 18 18 18 18 18 21