分数: 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.