AT_abc362_c [ABC362C] Sum = 0

题目描述

给定 $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$。

如果存在，请输出任意一个满足条件的序列。

输入格式

输入以如下格式从标准输入读入。

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

如果不存在满足条件的序列，输出 No。

如果存在，输出 Yes，并在同一行输出满足条件的整数序列 $X_1\ X_2\ \ldots\ X_N$。

如果有多个答案，输出任意一个均可。

输入输出样例 #1

输入 #1

3
3 5
-4 1
-2 3

输出 #1

Yes
4 -3 -1

输入输出样例 #2

输入 #2

3
1 2
1 2
1 2

输出 #2

No

输入输出样例 #3

输入 #3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

输出 #3

Yes
-66 -57 31 -6 89 9

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq L_i \leq R_i \leq 10^9$
• 所有输入均为整数

样例解释 1

数列 $X=(4,-3,-1)$ 满足所有条件。其他如 $(3,-3,0)$ 或 $(5,-4,-1)$ 也满足条件。

样例解释 2

不存在满足条件的整数序列 $X$。

由 ChatGPT 4.1 翻译