/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の整数組 (L_1, R_1), (L_2, R_2), \dots, (L_N, R_N) が与えられます．ここで，全ての 1\leq i\leq N に対して L_i \leq R_i が満たされています．
N 個の整数からなる列 A = (A_1, A_2, \ldots, A_N) であって，以下の条件を満たすものを良い整数列と呼びます．
- 全ての 1\leq i\leq N に対して，L_i \leq A_i \leq R_i である．
\displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| を最小にするような良い整数列 A のうち，辞書順で最小のものを求めてください．
数列の辞書順とは
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います． ここで，|S|, |T| はそれぞれ S, T の長さを表します．
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})．
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して，下記の 2 つがともに成り立つ．
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})．
- S_i が T_i より（数として）小さい．
制約
- 入力される数値は全て整数
- 2 \leq N \leq 5 \times 10^5
- 0 \leq L_i \leq R_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる．
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
答えを以下の形式で 1 行に出力せよ．
A_1 A_2 \ldots A_N
入力例 1
4 1 10 8 13 3 4 5 20
出力例 1
8 8 4 5
(A_1, A_2, A_3, A_4) = (8, 8, 4, 5) は良い整数列です．このとき \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| = |8 - 8| + |4 - 8| + |5 - 4| = 5 となり，これが \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| の最小の値です．
入力例 2
3 20 24 3 24 1 75
出力例 2
20 20 20
\sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| が最小となる良い数列 A が複数あるときは，そのうち辞書順で最小のものを出力することに注意してください．
入力例 3
15 335279264 849598327 446755913 822889311 526239859 548830120 181424399 715477619 342858071 625711486 448565595 480845266 467825612 647639160 160714711 449656269 336869678 545923679 61020590 573085537 626006012 816372580 135599877 389312924 511429216 547865075 561330066 605997004 539239436 921749002
出力例 3
526239859 526239859 526239859 467825612 467825612 467825612 467825612 449656269 449656269 449656269 626006012 389312924 511429216 561330066 561330066
Score: 600 points
Problem Statement
You are given N pairs of integers (L_1, R_1), (L_2, R_2), \dots, (L_N, R_N). Here, L_i \leq R_i for all 1 \leq i \leq N.
A sequence of N integers A = (A_1, A_2, \ldots, A_N) is called a good integer sequence if it satisfies the following condition:
- L_i \leq A_i \leq R_i for all 1 \leq i \leq N.
Find the lexicographically smallest good integer sequence A that minimizes \displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|.
What is lexicographical order for sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if 1. or 2. below holds. Here, |S|, |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- All input values are integers.
- 2 \leq N \leq 5 \times 10^5
- 0 \leq L_i \leq R_i \leq 10^9
Input
The 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 answer in a single line in the following format:
A_1 A_2 \ldots A_N
Sample Input 1
4 1 10 8 13 3 4 5 20
Sample Output 1
8 8 4 5
(A_1, A_2, A_3, A_4) = (8, 8, 4, 5) is a good integer sequence. In this case, \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}| = |8 - 8| + |4 - 8| + |5 - 4| = 5, which is the minimum value of \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|.
Sample Input 2
3 20 24 3 24 1 75
Sample Output 2
20 20 20
Note that when multiple good integer sequences A minimize \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|, you should print the lexicographically smallest of them.
Sample Input 3
15 335279264 849598327 446755913 822889311 526239859 548830120 181424399 715477619 342858071 625711486 448565595 480845266 467825612 647639160 160714711 449656269 336869678 545923679 61020590 573085537 626006012 816372580 135599877 389312924 511429216 547865075 561330066 605997004 539239436 921749002
Sample Output 3
526239859 526239859 526239859 467825612 467825612 467825612 467825612 449656269 449656269 449656269 626006012 389312924 511429216 561330066 561330066