#G1059. [GESP202406 八级] 空间跳跃

[GESP202406 八级] 空间跳跃

[GESP202406 八级] 空间跳跃

题目描述

小杨在二维空间中有 nn 个水平挡板,并且挡板之间彼此不重叠,其中第 ii 个挡板处于水平高度 hih_i,左右端点分别位于 lil_i 与 rir_i。

小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动 11 个单位长度会耗费 11 个单位时间,掉落时每掉落 11 个单位高度也会耗费 11 个单位时间。

小杨想知道,从第 ss 个挡板上的左端点出发到第 tt 个挡板需要耗费的最少时间是多少?

注意:可能无法从第 ss 个挡板到达第 tt 个挡板。

输入格式

第一行包含一个正整数 nn,代表挡板数量。

第二行包含两个正整数 s,ts, t,含义如题面所示。

之后 nn 行,每行包含三个正整数 li,ri,hil_i, r_i, h_i,代表第 ii 个挡板的左右端点位置与高度。

输出格式

输出一个整数代表需要耗费的最少时间,如果无法到达则输出 −1-1。

样例 #1

样例输入 #1

3
3 1
5 6 3
3 5 6
1 4 100000

样例输出 #1

100001

样例解释

耗费时间最少的移动方案为,从第 33 个挡板左端点移动到右端点,耗费 33 个单位时间,然后向右移动掉落到第 22 个挡板上,耗费 100000−6=99994100000 - 6 = 99994 个单位时间,之后再向右移动 11 个单位长度,耗费 11 个单位时间,最后向右移动掉落到第 11 个挡板上,耗费 33 个单位时间。共耗费 3+99994+1+3=1000013 + 99994 + 1 + 3 = 100001 个单位时间。

数据范围

子任务编号 数据点占比 nn 特殊条件
1 20% ≤1000≤ 1000 li=1l_i = 1
2 40% li=il_i = i,ri=i+1r_i = i + 1
3 无
  • 对于全部数据,保证有 1≤n≤10001 ≤ n ≤ 1000,1≤li≤ri≤1051 ≤ l_i ≤ r_i ≤ 10^5,1≤hi≤1051 ≤ h_i ≤ 10^5。

时间限制:1.0 s。内存限制:512.0 MB。