← 返回题目列表

AtCoder · arc175_c

C. 跳跃区间

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你被给予 N 整数对 (L_1, R_1), (L_2, R_2), \dots, (L_N, R_N)。在这里, L_i \leq R_i 对于所有人 1 \leq i \leq N.

一系列 N 整数 A = (A_1, A_2, \ldots, A_N) 被称为 好的整数序列 如果满足以下条件:

  • L_i \leq A_i \leq R_i 对于所有人 1 \leq i \leq N.

查找字典顺序最小的 好的整数序列 A 最小化 \displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|.

序列的字典顺序是什么?

一个序列 正整数(可能为空)的 S = (S_1,S_2,\ldots,S_{|S|}) 据说是 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果下面的 1. 或 2. 成立。 在这里, |S|, |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • (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

输出

按以下格式在一行中打印答案:

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

请注意,当多个好的整数序列 A 最小化 \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|,您应该打印其中按字典顺序最小的一个。


示例输入 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