配点 : 1000 点
問題文
有 N 颗星星,按坐标递减顺序排列。 它们的编号最大为 1 从 N 。明星 i \ (1 \leq i \leq N) 是坐标 X_i 亮度为 A_i 。
AtCoder 想要拍摄一些明星的照片。 AtCoder 在数轴上选择一个他喜欢的区间,并拍摄其中包含的星星。在这里,照片中的多颗星星可能太亮而无法等同。这遵循以下规则。
- 星 i, j 是 如果\left|X_i - X_j\right| \leq A_i + A_j 满足,则相等
- 星 i, k 已被识别并且星星 当 k, j 被识别时,星星 i, j 等于
- 未按照上述规则识别的星星将在照片中显示为不同的星星。
请注意,未落在拍摄区域内的星星不会出现在照片中。甚至不需要身份识别 请注意。
现在,如果你选择好拍摄区域,你能在照片中捕捉到多少颗不同的星星? 您将获得
T 测试用例,因此请找到每个测试用例的答案。 在
制約
- T \geq 1
- 1 \leq N \leq 200\,000
- 0 \leq X_1 < \dots < X_N \leq 10^8
- 1 \leq A_i \leq 10^8
- T 测试用例中 N 的总和是 200\,000 以下
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。这里 这意味着第 \mathrm{case}_i 为 i 个测试用例。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。
N X_1 A_1 X_2 A_2 \vdots X_N A_N
出力
请打印答案。
入力例 1
3 4 0 1 3 1 6 5 9 1 6 0 3 1 1 4 1 6 1 9 1 10 3 5 10 5 20 5 30 5 40 5 50 5
出力例 1
2 3 1
1 如何在测试用例中拍照 2 如下所示。
- 坐标是 0 以上 5 如果选择以下间隔:星形 照片中将出现 1, 2 。|X_1 - X_2| = 3, A_1 + A_2 = 2 因此,明星 1, 2 在照片中显示为一颗单独的星星。 照片中将出现
- 坐标是 0 以上 9 如果选择以下间隔:星形 照片中将出现 1, 2, 3, 4 。由于问题陈述中的第一条规则,星号 1, 3、星 2, 3、星 3, 4 将被等同。那么,根据问题中的第二条规则,星星 1, 2, 3, 4 被识别为一颗星。
在这个测试用例中,最多 2 可以拍成两颗不同的星星,一种方法是方法1.2.方法中 1 这不是最好的选择,因为它会在照片中显示为一颗星星。 对于第
2 个测试用例,最多 3 一种方法是指定星星的坐标。 1 以上 9 可以使用以下方法来选择间隔。 在第
3 个测试用例中,无论你如何选择包含星号的区间,1 它将在照片中显示为两颗星。