P8246 [COCI 2013/2014 #3] TRANSMITTERS

On a 2D plane, there is a line segment $L$ of length $d$, whose left endpoint is at the origin, and which lies on the $x$ axis. There are also $n$ segments $l_1, l_2, \cdots, l_n$ that are perpendicular to the $x$ axis, whose feet lie on segment $L$, and which are above the $x$ axis. For the $i$-th segment, its distance from the origin is $x_i$, and its length is $h_i$. Besides segment $L$, the top endpoints of some segments have a negligible-sized light point installed, which can emit lasers to its left and right. A laser can only travel along a straight line, and it cannot pass through any segment (including segment $L$). We say a point $A$ on segment $L$ is covered if and only if there exists some light point such that it emits a laser in some direction and the laser finally lands on point $A$. Now, compute the total length of all covered parts on segment $L$. Please refer to the samples and sample explanations to better understand the statement.

The first line contains two integers $n, d$, representing the number of segments **other than segment $L$** and the length of segment $L$, respectively. The next $n$ lines each contain three integers $op_i, x_i, h_i$, representing whether the top endpoint of the $i$-th segment has a light point, the distance of the $i$-th segment from the origin, and its length. Specifically, if $op_i = 0$, it means the top endpoint of the $i$-th segment has no light point; otherwise, it means the top endpoint has a light point.

Output a **real number**, the total length of all covered parts on segment $L$. You must ensure that the relative error between your output and the standard answer does not exceed $10^{-3}$.

**Sample 2 Explanation** The figure below corresponds to sample 2, where the bold parts are the **uncovered areas**.  **Constraints and Limits** **This problem uses bundled testdata**. The score and special limits for each subtask are as follows: - Subtask 1 (48 pts): $n \leqslant 10^3$. - Subtask 2 (112 pts): no special limits. For all testdata, $1 \leqslant n \leqslant 3 \times 10^5$, $1 \leqslant d \leqslant 10^9$, $op_i \in \{0, 1\}$, $0 \leqslant x_i \leqslant d$, $1 \leqslant h_i \leqslant 10^9$. It is guaranteed that $\forall i \neq j$, $x_i \neq x_j$. It is guaranteed that $x_i$ is strictly increasing. **Source** This problem is from **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T6 ODAŠILJAČI_**, and with the original data configuration, the full score is $160$ points. Translated, organized, and provided by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5