Removing Robots

题目描述

数线上有编号为 $1$ 到 $N$ 的 $N$ 个机器人。机器人 $i$ 放置在坐标 $X_i$。当被激活时，它会向正方向移动距离 $D_i$，然后从数线上被移除。所有机器人以相同的速度移动，且它们的大小可忽略不计。 爱捣蛋的高桥可以在数线上仍有机器人存在的情况下任意多次（可能为零次）执行以下操作。

选择一个机器人并激活它。当有机器人在移动时，不能执行此操作。

当机器人 $i$ 在移动时，如果它接触到数线上仍然停留在区间 $[X_i, X_i + D_i)$ 内的另一个机器人 $j$，机器人 $j$ 也会被激活并开始移动。该过程会递归重复。 在高桥进行若干次操作后，数线上可能剩下的机器人的集合有多少种？由于答案可能非常大，请对 $998244353$ 取模后输出该计数。

输入格式

输入按下述格式从标准输入给出： $N$ $X_1$ $D_1$ : $X_N$ $D_N$

输出格式

输出在高桥进行若干次操作后，数线上可能剩下的机器人的集合数目，对 $998244353$ 取模。

2
1 5
3 3

3

3
6 5
-1 10
3 3

5

4
7 10
-10 3
4 3
-4 3

16

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

110

提示

$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)$ 输入中的所有数值均为整数。可能剩下的机器人集合有三种：$\{1, 2\}$、$\{1\}$ 和 $\{\}$。 可以如下实现这些状态：

如果高桥什么都不激活，则机器人 $\{1, 2\}$ 会剩下。

如果高桥激活机器人 $1$，它在移动时会激活机器人 $2$，之后数线上将没有机器人。该状态也可以通过先激活机器人 $2$ 再激活机器人 $1$ 达到。

如果高桥激活机器人 $2$ 并结束操作，则机器人 $\{1\}$ 会剩下。
可能剩下的机器人集合有五种：$\{1, 2, 3\}$、$\{1, 2\}$、$\{2\}$、$\{2, 3\}$ 和 $\{\}$。
没有机器人相互影响。
记得对 $998244353$ 取模后输出答案。

标签: AtCoder|abc158F

来源

AtCoder|abc158F