← 返回题目列表

Codeforces · 269/D

D. 最大瀑布

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

Emuskald 受雇根据景观设计的最新趋势设计人工瀑布。现代人工瀑布由固定在宽阔平坦墙壁上的多个水平面板组成。水沿着墙的顶部从一个面板流到另一个面板,直到到达墙的底部。

墙的高度为 t,墙上有 n 个面板。每个面板都是高度为 hi 的水平段,从 li 开始,到 ri 结束。第 i 个面板连接平面的点 (li, hi) 和 (ri, hi)。墙的顶部可以被认为是连接点(-109,t)和(109,t)的面板。类似地,墙的底部可以被认为是连接点(-109,0)和(109,0)的面板。没有两个面板有共同点。

Emuskald 知道,为了使瀑布美观,只有满足以下条件,它才能从面板 i 流向面板 j ($$\vec{i} \rightarrow \vec{j}$$):

1. max(li, lj) < min(ri, rj)(面板的水平投影重叠);
2. hj < hi(面板j在面板i下方);
3. 对于 (i, k) 和 (k, j) 对,不存在前两个条件成立的面板 k (hj < hk < hi)。

那么 $$\vec{i} \rightarrow \vec{j}$$ 的流量等于 min(ri, rj) - max(li, lj),即它们水平投影重叠的长度。

Emuskald 决定在他的瀑布中,水将从上到下沿单一路径流动。如果水流到一块面板(除了墙的底部),水会进一步落到正好一个较低的面板。然后,瀑布中的水流总量定义为瀑布路径中两个连续面板之间的最小水平投影重叠。正式:

1. 瀑布由单条路径的面板组成 $$top \rightarrow p_1 \rightarrow p_2 \rightarrow \ldots \rightarrow Bottom$$;
2.瀑布的流量是$$top \rightarrow p_1 \rightarrow p_2 \rightarrow \ldots \rightarrow Bottom$$路径中的最小流量。

要制作真正伟大的瀑布,Emuskald 必须最大化水流,但面板太多,他很难规划自己的创作。以下是 Emuskald 想要的瀑布示例:

帮助Emuskald维护他的声誉并找到最大可能水流的值。

输入

输入的第一行包含两个空格分隔的整数 n 和 t (1 ≤ n ≤ 105, 2 ≤ t ≤ 109)、不包括顶部和底部面板的面板数量以及墙壁的高度。接下来的 n 行中的每一行包含三个空格分隔的整数 hi、li 和 ri (0 < hi < t, - 109 ≤ li < ri ≤ 109),即第 i 个面板段的高度、左端和右端。

保证没有两个线段共享公共点。

输出

输出一个整数 - 所需瀑布中可能的最大水流量。

示例

输入 #1

5 6
4 1 6
3 2 7
5 9 11
3 10 15
1 13 16

输出 #1

4

输入 #2

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

输出 #2

2

注意

第一个测试用例对应图片。