#P1442. 铁球落地

铁球落地

题目描述

在二维坐标系内有 nn 个平台(定义平台是一条两端点纵坐标相同的开线段,开线段指线段两个端点不算做线段本身)和一个铁球,铁球如果下面没有物体,则每秒会下落一个单位长度。

球每次落到某个平台上后,游戏者可以选择水平向左或水平向右滚,球滚动速度是每秒 11 个单位长度。由于铁球的质量不太好,每次落下的高度不能超过 hh

设计一种策略,使得球尽快落到地面而不被摔碎。

假设地面高度为 00,且无限宽。球体积相对平台极小,可以看作一个质点。请注意,球滚动至平台的一个端点处即可下落,不需要滚动至下一个格子。例如下图,小球在 (9,9)(9,9) 处已经开始下落。

输入格式

第一行有两个整数,分别代表平台个数 nn 和最大下落高度 hh

第二行有两个整数 x,yx, y,表示铁球起始时在坐标为 (x,y)(x, y) 的位置。

33 到第 (n+2)(n + 2) 行,每行三个整数,第 (i+2)(i + 2) 行的整数 hi,li,rih_i, l_i, r_i 分别代表第 ii 个平台的端点纵坐标 hih_i 和左右端点的横坐标 li,ril_i,r_i

输出格式

输出一行一个整数表示最小的坠落时间。

5 3
6 10
5 2 4
9 3 9
6 7 10
2 1 5
3 8 11

15
10 156
84 139
63 22 50
79 96 100
87 77 98
60 24 53
47 1 29
62 55 89
68 68 78
10 5 85
85 67 71
73 57 61

155

提示

数据规模与约定

对于全部的测试点,保证:

  • 1n1051 \leq n \leq 10^5
  • 1x,y,h,hi,li,ri1091 \leq x, y, h, h_i, l_i, r_i \leq 10^9liril_i \leq r_i
  • 对于所有的 hih_i,保证互不相同,lil_irir_i 也互不相同,且对于任意 iji \neq j,保证 lirjl_i \neq r_j
  • 数据保证有解,最终答案不超过 10910^9