← 返回题目列表

Codeforces · 1209/H

H. 自动人行道

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

机场经常使用自动人行道来帮助您更快地行走长距离。每条这样的走道都有一定的速度,可以有效地提高您的速度。你可以站在这样的走道上,让它移动你,或者你也可以步行,那么你的有效速度就是你的行走速度加上走道的速度。

Limak 想要从点 $$$0$$$ 到点 $$$L$$$ 在一条直线上。其间有 $$$n$$$ 不相交的走道。第 $$$i$$$ 走道由两个整数 $$$x_i$$$ 和 $$$y_i$$$ 以及一个实值 $$$s_i$$$ 描述。第 $$$i$$$ 走道起始于 $$$x_i$$$,结束于 $$$y_i$$$,速度为 $$$s_i$$$。

每条走道都位于 $$$[0, L]$$$ 段内,并且没有两条走道有正交集。然而,它们可以通过端点接触。

利马克需要决定如何分配他的能量。例如,站在某个地方(或缓慢行走)然后有大量能量走得更快可能更有意义。

Limak 的初始能量为 $$$0$$$ 并且它绝不能低于该值。任何时刻,他可以在$$$[0, 2]$$$区间内以任意速度$$$v$$$行走,每秒会消耗$$$v$$$能量,但他会以每秒$$$1$$$能量的速度持续恢复能量。因此,当他以 $$$v$$$ 速度行走时,他的能量会增加 $$$(1-v)$$$。请注意,负值意味着损失能量。

特别是,他可以以 $$$1$$$ 的速度行走,这根本不会改变他的能量,而以 $$$0.77$$$ 的速度行走实际上为他每秒提供 $$$0.23$$$ 能量。

Limak可以在每个时刻(包括他位于非整数位置的时刻)任意选择他的速度($$$[0, 2]$$$区间内的任意实值)。一切都是连续的(非离散的)。

Limak 从 $$$0$$$ 到 $$$L$$$ 最快需要多少时间?

输入

第一行包含整数 $$$n$$$ 和 $$$L$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le L \le 10^9$$$)、走道数量和步行距离。

接下来的 $$$n$$$ 行包含整数 $$$x_i$$$、$$$y_i$$$ 和实际值 $$$s_i$$$ ($$$0 \le x_i < y_i \le L$$$, $$$0.1 \le s_i \le 10.0$$$)。值 $$$s_i$$$ 的小数点后最多为 $$$9$$$ 位。

可以保证,没有两条走道有正交点。走道从左到右列出。也就是说,$$$y_i \le x_{i + 1}$$$ 对于 $$$1 \le i \le n - 1$$$。

输出

打印一个实际值,即达到 $$$L$$$ 的最快时间。如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则您的答案将被视为正确。

示例

输入 #1

1 5
0 2 2.0

输出 #1

3.000000000000

输入 #2

1 5
2 4 0.91

输出 #2

3.808900523560

输入 #3

3 1000
0 990 1.777777
995 996 1.123456789
996 1000 2.0

输出 #3

361.568848429553

注意

附图显示了前两个示例。在第一个中,有一条从 $$$0$$$ 到 $$$2$$$ 的走道,速度为 $$$2.0$$$,Limak 想要到达点 $$$5$$$。第二个示例有一条从 $$$2$$$ 到 $$$4$$$ 的走道,速度为 $$$0.91$$$。

在第一个示例中,最佳策略之一如下。

- 站在人行道上,从 $$$0$$$ 到达 $$$2$$$。它以 $$$2$$$ 的速度移动您,因此需要 $$$1$$$ 秒,并且您可以节省 $$$1$$$ 能量。
- 在接下来的 $$$1$$$ 秒内以最大速度 $$$2$$$ 行走,从 $$$2$$$ 到达 $$$4$$$。再次花费 $$$1$$$ 秒,能量降至 $$$0$$$。
- 以 $$$1$$$ 速度步行,从 $$$4$$$ 到达 $$$5$$$。需要 $$$1$$$ 秒,能量保持恒定在 $$$0$$$ 值。

总时间为 $$$1 + 1 + 1 = 3$$$。