← 返回题目列表

Codeforces · 1552/F

F. 气喘吁吁

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

一只蚂蚁在实线上以每秒 $$$1$$$ 单位的恒定速度移动。它从 $$$0$$$ 开始并始终向右移动(因此其位置每秒增加 $$$1$$$)。

有 $$$n$$$ 个传送门,其中第 $$$i$$$ 位于位置 $$$x_i$$$ 并传送到位置 $$$y_i < x_i$$$。每个门户可以是活动的或非活动的。第 $$$i$$$ 个门户的初始状态由 $$$s_i$$$ 确定:如果 $$$s_i=0$$$ 则第 $$$i$$$ 个门户最初处于非活动状态,如果 $$$s_i=1$$$ 则第 $$$i$$$ 个门户最初处于活动状态。当蚂蚁穿过传送门时(即,当它的位置与传送门的位置重合时):

- 如果门户处于非活动状态,它将变为活动状态(在这种情况下,蚂蚁的路径不受影响);
- 如果传送门处于活动状态,它将变为非活动状态,并且蚂蚁会立即传送到位置 $$$y_i$$$,并在那里继续正常移动。

蚂蚁需要多长时间(从开始移动的那一刻起)到达$$$x_n + 1$$$位置?可以证明这发生在有限的时间内。由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模进行计算。

输入

第一行包含整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 门户数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$s_i$$$ ($$$1\le y_i < x_i\le 10^9$$$, $$$s_i\in\{0,1\}$$$) — 的位置第 $$$i$$$ 个传送门、蚂蚁穿过第 $$$i$$$ 个传送门时传送的位置(如果它处于活动状态)以及第 $$$i$$$ 个传送门的初始状态。

传送门的位置严格递增,即$$$x_1<x_2<\cdots<x_n$$$。保证 $$$2n$$$ 整数 $$$x_1, \, x_2, \, \dots, \, x_n, \, y_1, \, y_2, \, \dots, \, y_n$$$ 都是不同的。

输出

输出从蚂蚁开始移动到到达位置 $$$x_n+1$$$ 所经过的时间(以秒为单位)。由于答案可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

示例

输入 #1

4
3 2 0
6 5 1
7 4 0
8 1 1

输出 #1

23

输入 #2

1
454971987 406874902 1

输出 #2

503069073

输入 #3

5
243385510 42245605 0
644426565 574769163 0
708622105 208990040 0
786625660 616437691 0
899754846 382774619 0

输出 #3

899754847

输入#4

5
200000000 100000000 1
600000000 400000000 0
800000000 300000000 0
900000000 700000000 1
1000000000 500000000 0

输出#4

3511295

注意

第一个样本的解释:蚂蚁的移动方式如下(弯曲箭头表示传送,直箭头表示正常移动,速度为$$$1$$$,移动过程中所花费的时间写在箭头上方)。 $$$$$$ 0 \stackrel{6}{\longrightarrow} 6 \leadsto 5 \stackrel{3}{\longrightarrow} 8 \leadsto 1 \stackrel{2}{\longrightarrow} 3 \leadsto 2 \stackrel{4}{\longrightarrow} 6 \leadsto 5 \stackrel{2}{\longrightarrow} 7 \leadsto 4 \stackrel{2}{\longrightarrow} 6 \leadsto 5 \stackrel{4}{\longrightarrow} 9 $$$$$$ 请注意,总时间为 $$$6+3+2+4+2+2+4=23$$$。

第二个样本的解释:蚂蚁的移动方式如下(弯曲箭头表示传送,直箭头表示正常移动,速度为$$$1$$$,移动过程中所花费的时间写在箭头上方)。 $$$$$$ 0 \stackrel{454971987}{\longrightarrow} 454971987 \leadsto 406874902 \stackrel{48097086}{\longrightarrow} 454971988 $$$$$$ 请注意,总时间为$$$454971987+48097086=503069073$$$。

第三个样本的解释:由于所有传送门最初都是关闭的,所以蚂蚁不会被传送,而是会直接从$$$0$$$到达$$$x_n+1=899754846+1=899754847$$$。