/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます。
以下の条件を満たす長さ N の整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するならば一つ出力してください。
- 各 i=1,2,\ldots,N に対して L_i\leq X_i\leq R_i
- \displaystyle \sum_{i=1}^N X_i=0
制約
- 1\leq N\leq 2\times 10^5
- -10^9\leq L_i\leq R_i\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
存在しない場合は No を出力せよ。存在する場合は条件を満たす整数列 X を以下の形式で出力せよ。
Yes X_1 X_2 \ldots X_N
答えが複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 3 5 -4 1 -2 3
出力例 1
Yes 4 -3 -1
数列 X=(4,-3,-1) は問題の条件をすべて満たします。ほかにも (3,-3,0) や (5,-4,-1) などが条件を満たします。
入力例 2
3 1 2 1 2 1 2
出力例 2
No
条件を満たす整数列 X は存在しません。
入力例 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
出力例 3
Yes -66 -57 31 -6 89 9
Score : 350 points
Problem Statement
You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).
Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.
- L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
- \displaystyle \sum_{i=1}^N X_i = 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq L_i \leq R_i \leq 10^9
- All input values are integers.
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
If no solution exists, print No. Otherwise, print an integer sequence X that satisfies the conditions in the following format:
Yes X_1 X_2 \ldots X_N
If multiple solutions exist, any of them will be considered correct.
Sample Input 1
3 3 5 -4 1 -2 3
Sample Output 1
Yes 4 -3 -1
The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).
Sample Input 2
3 1 2 1 2 1 2
Sample Output 2
No
No sequence X satisfies the conditions.
Sample Input 3
6 -87 12 -60 -54 2 38 -76 6 87 96 -17 38
Sample Output 3
Yes -66 -57 31 -6 89 9