← 返回题目列表

AtCoder · abc158_f

F. 移除机器人

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

分数: 600 点

问题陈述

有 N 机器人编号 1 to N 放置在数轴上。机器人 i 放置在坐标处 X_i。激活后,它将行驶的距离 D_i 向正方向移动,然后将其从数轴上移除。所有机器人都以相同的速度移动,并且它们的大小可以忽略不计。

高桥是一个淘气的男孩,只要数轴上还剩下一个机器人,他就可以执行以下操作任意次数(可能为零)。

  • 选择一个机器人并激活它。当机器人正在移动时,无法执行此操作。

虽然机器人 i 正在移动,如果它接触到另一个机器人 范围内剩余的 j 范围内剩余的 [X_i, X_i + D_i) 在数轴上,机器人 j 也被激活并开始移动。递归地重复该过程。

高桥进行多次运算后,数轴上剩余的机器人可能有多少组?计算该计数的模数 998244353,因为它可能是巨大的。

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • 输入中的所有值都是整数。

输入

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

N
X_1 D_1
:
X_N D_N

输出

打印数轴上剩余的可能的机器人组数,模数 998244353.


示例输入 1

2
1 5
3 3

示例输出 1

3

数轴上剩余三组可能的机器人: \{1, 2\}, \{1\},和 \{\}.

这些可以通过以下方式实现:

  • 如果高桥没有激活任何东西,机器人 \{1, 2\} 将保留。

  • 如果高桥启动机器人 1,它将激活机器人 2 移动时,之后数轴上将不再有机器人。也可以通过激活 Robot 来达到此状态 2 然后机器人 1.

  • 如果高桥启动机器人 2 并完成操作,机器人 \{1\} 将保留。


示例输入 2

3
6 5
-1 10
3 3

示例输出 2

5

数轴上剩余五组可能的机器人: \{1, 2, 3\}, \{1, 2\}, \{2\}, \{2, 3\},和 \{\}.


示例输入 3

4
7 10
-10 3
4 3
-4 3

示例输出 3

16

机器人不会影响其他机器人。


示例输入 4

20
-8 1
26 4
0 5
9 1
19 4
22 20
28 27
11 8
-3 20
-25 17
10 4
-18 27
24 28
-11 19
2 27
-2 18
-1 12
-24 29
31 29
29 7

示例输出 4

110

记住打印计数模数 998244353.