Moving Walkways
Contest: Codeforces Round 584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: data structures, greedy, math

Airports often use moving walkways to help you walking big distances faster. Each such walkway has some speed that effectively increases your speed. You can stand on such a walkway and let it move you, or you could also walk and then your effective speed is your walking speed plus walkway's speed.

Limak wants to get from point $$$0$$$ to point $$$L$$$ on a straight line. There are $$$n$$$ disjoint walkways in between. The $$$i$$$-th walkway is described by two integers $$$x_i$$$ and $$$y_i$$$ and a real value $$$s_i$$$. The $$$i$$$-th walkway starts at $$$x_i$$$, ends at $$$y_i$$$ and has speed $$$s_i$$$.

Every walkway is located inside the segment $$$[0, L]$$$ and no two walkways have positive intersection. However, they can touch by endpoints.

Limak needs to decide how to distribute his energy. For example, it might make more sense to stand somewhere (or to walk slowly) to then have a lot of energy to walk faster.

Limak's initial energy is $$$0$$$ and it must never drop below that value. At any moment, he can walk with any speed $$$v$$$ in the interval $$$[0, 2]$$$ and it will cost him $$$v$$$ energy per second, but he continuously recovers energy with speed of $$$1$$$ energy per second. So, when he walks with speed $$$v$$$, his energy increases by $$$(1-v)$$$. Note that negative value would mean losing energy.

In particular, he can walk with speed $$$1$$$ and this won't change his energy at all, while walking with speed $$$0.77$$$ effectively gives him $$$0.23$$$ energy per second.

Limak can choose his speed arbitrarily (any real value in interval $$$[0, 2]$$$) at every moment of time (including the moments when he is located on non-integer positions). Everything is continuous (non-discrete).

What is the fastest time Limak can get from $$$0$$$ to $$$L$$$?

Input format:
The first line contains integers $$$n$$$ and $$$L$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le L \le 10^9$$$), the number of walkways and the distance to walk.

Each of the next $$$n$$$ lines contains integers $$$x_i$$$, $$$y_i$$$ and real value $$$s_i$$$ ($$$0 \le x_i < y_i \le L$$$, $$$0.1 \le s_i \le 10.0$$$). The value $$$s_i$$$ is given with at most $$$9$$$ digits after decimal point.

It's guaranteed, that no two walkways have a positive intersection. The walkways are listed from left to right. That is, $$$y_i \le x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$.

Output format:
Print one real value, the fastest possible time to reach $$$L$$$. Your answer will be considered correct if its absolute or relative error won't exceed $$$10^{-9}$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
The drawings show the first two examples. In the first one, there is a walkway from $$$0$$$ to $$$2$$$ with speed $$$2.0$$$ and Limak wants to get to point $$$5$$$. The second example has a walkway from $$$2$$$ to $$$4$$$ with speed $$$0.91$$$.

In the first example, one of optimal strategies is as follows.

- Get from $$$0$$$ to $$$2$$$ by standing still on the walkway. It moves you with speed $$$2$$$ so it takes $$$1$$$ second and you save up $$$1$$$ energy.
- Get from $$$2$$$ to $$$4$$$ by walking with max speed $$$2$$$ for next $$$1$$$ second. It takes $$$1$$$ second again and the energy drops to $$$0$$$.
- Get from $$$4$$$ to $$$5$$$ by walking with speed $$$1$$$. It takes $$$1$$$ second and the energy stays constant at the value $$$0$$$.

The total time is $$$1 + 1 + 1 = 3$$$.

Example input:
1 5
0 2 2.0

Example output:
3.000000000000

Example input:
1 5
2 4 0.91

Example output:
3.808900523560

Editorial:
Some minor tips:
• Everything is a walkway. When there is no walkway, it is a walkway of speed $$$0$$$.
• You can increase all speeds by $$$1$$$ and assume that you own speed is in $$$[-1; +1]$$$
• Energy is an entity which is "$$$\delta$$$speed $$$\times$$$ time, which is distance.
Also if you spend $$$x$$$ energy per segment of len $$$l$$$ and speed $$$v$$$, it is not important how exactly you will distribute it over the walking process. In any way, you will walk by feet $$$l - x$$$ meters with speed $$$(l - x) / v$$$.
So it turns out it's better to distribute more energy to low-speeded walkways (because the denominator is smaller).
Assume that you (by default) save up all energy on any non-feet path (for feet path it's always optimal to walk with speed $$$\ge 1$$$ ($$$\ge 0$$$ after speeds hack), so now save up's).
Build an energy graphic where the Ox axis will correspond to the point you are in (not time). It will be a piecewise linear function, so it is enough to store it's value only in points corresponding to points between walkways. Iterate over walkways in the order of speed and try to steal as much energy as possible to the current walkway.
What are the limits of stealing energy?
• there is a restriction based on $$$l$$$ and $$$v$$$ (if you take too much energy, you wouldn't be able to fully walk it up)
• the graphic must still be able above $$$0$$$ at all points.
The latter condition is just a suffix minima on a segment tree.
Complexity: $$$\mathcal{O}(n \log n)$$$.