Preparando MOJI
You are given $$$n$$$ segments on a number line, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th segments covers all integer points from $$$l_i$$$ to $$$r_i$$$ and has a value $$$w_i$$$.
You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point $$$m$$$ starting from point $$$1$$$ in arbitrary number of moves.
The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.
In every test there exists at least one good subset.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^6$$$) — the number of segments and the number of integer points.
Each of the next $$$n$$$ lines contains three integers $$$l_i$$$, $$$r_i$$$ and $$$w_i$$$ ($$$1 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 10^6$$$) — the description of the $$$i$$$-th segment.
In every test there exists at least one good subset.
Print a single integer — the minimum cost of a good subset.
5 12 1 5 5 3 4 10 4 10 6 11 12 5 10 12 3
3
1 10 1 10 23
0
Informação
Provedor Codeforces
Código CF1555E
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:16:19
Relacionados