← 返回题目列表

AtCoder · abc325_d

G. 印刷机

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

分数: 450 点

问题陈述

有 N 产品贴有标签 1 to N 在传送带上流动。 Keyence 打印机连接到传送带上,并且产品 i 进入打印机的范围 T_i 从现在开始微秒并离开它 D_i 微秒后。

Keyence 打印机可以立即在打印机范围内的一件产品上进行打印(特别是,可以在产品进入或离开打印机范围时进行打印)。 然而,打印一次后,需要充电时间 1 微秒后才能再次打印。 当选择最佳的产品和打印机打印时间时,打印机最多可以打印多少个产品?

约束

  • 1\leq N \leq 2\times 10^5
  • 1\leq T_i,D_i \leq 10^{18}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
T_1 D_1
T_2 D_2
\vdots
T_N D_N

输出

打印打印机可以打印的最大产品数量。


样本输入 1

5
1 1
1 1
2 1
1 2
1 4

示例输出 1

4

下面,我们将简单地调用该时刻 t 从现在开始的微秒时间 t.

例如,您可以在四种产品上打印,如下所示:

  • 时间 1 :产品 1,2,4,5 输入打印机的范围。在产品上打印 4.
  • 时间 2 :产品 3 进入打印机范围,产品 1,2 离开打印机的范围。在产品上打印 1.
  • 时间 3 :产品 3,4 离开打印机的范围。在产品上打印 3.
  • 时间 4.5 : 在产品上打印 5.
  • 时间 5 :产品 5 离开打印机的范围。

不可能在所有五种产品上打印,所以答案是 4.


示例输入 2

2
1 1
1000000000000000000 1000000000000000000

示例输出 2

2

示例输入 3

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

示例输出 3

6