1548 : 爆竹声中迎新年

时间限制:1 Sec 内存限制:256 MiB 提交:40 正确:14

提交 状态 论坛

题目描述

2023年将至,为了迎接新的一年,小强特地跑到国外买了很多鞭炮。每逢新年,小强都会放鞭炮,各种花样都被他尝试了个遍。因此,今年他想独创一种新的花样。众所周知,鞭炮爆炸的时候会有碎片崩出,这很可能会点燃另外一些还未点燃的鞭炮,被碎片点燃的鞭炮又可能会点燃另外一些未点燃的鞭炮......。现在他有n个鞭炮,每个鞭炮都有一个初始位置$x_i$,第i个鞭炮爆炸后会向左右两边崩出距离为$y_i$的两半碎片(一个碎片最多点燃一个鞭炮)。他想挑选位置最左边的鞭炮进行点燃,他想知道最终会有多少鞭炮发生爆炸?

输入描述

第一行输入n,代表有n个鞭炮。

接着n行,每行输入两个数 $x_i ,y_i$分别代表第i个鞭炮的初始位置,第i个鞭炮两半碎片的崩出距离。

数据约定:$1\leq n \leq 10^5$, $1\leq x_i \leq 10^9$ ,$1\leq y_i \leq 10^9$,保证$x_i$互不相同。

说明:第i个鞭炮的左右两半碎片的位置分别是$x_i-y_i+1$ 和 $x_i+y_i-1$。

输出描述

输出一个数,代表鞭炮爆炸数。

样例输入

4
4 5
3 2
8 4
5 3

样例输出

4

提示

样例解释:
首先小强点燃位置为3的鞭炮1;鞭炮1的右半碎片崩到位置4,点燃该处的鞭炮2;鞭炮2的右半碎片崩到位置8,点燃该处的鞭炮3;鞭炮3的左半碎片崩到位置5,点燃该处的鞭炮4。所以最终4个鞭炮全部爆炸,答案输出4。

来源

2023跨年赛