#P4272. physic 物理

    ID: 3488 传统题 3000ms 512MiB 尝试: 28 已通过: 9 难度: 8 上传者: 标签>难度分类提高+/省选-枚举与搜索广度优先搜索数据结构线段树套平衡树排序与序列处理二分查找离线与分治合并有序结果CF2400

physic 物理

physic 物理

题目描述

SG 和他的 n−1n-1 名同伴站在一条直线上。SG 编号为 11,位置为 00。对于第 ii 个人(2≤i≤n2\le i\le n),他能发出和接收的频率范围为 [xi,yi][x_i,y_i],所在位置为 sis_i。SG 可以接收任何频率。

一次传话耗时 11。发话者与收话者的距离必须不超过 LL,且发话者可以选择一个收话者能接收的频率。中转者收到后可以重新选择发出的频率。对每名同伴,求他把消息传给 SG 的最短时间。

输入格式

第一行两个整数 n,Ln,L。接下来 n−1n-1 行,依次给出第 22 至第 nn 个人的 xi,yi,six_i,y_i,s_i。

输出格式

输出 n−1n-1 行,第 i−1i-1 行是编号为 ii 的人传话给 SG 的最短时间。若无法传到,输出 -1。

样例 #1

样例输入 #1

3 1
1 2 1
2 3 2

样例输出 #1

1
2

样例说明

第 22 个人能直接传给 SG。第 33 个人可用频率 22 先传给第 22 个人,再由第 22 个人转达。

数据规模与约定

1≤n≤2500001\le n\le250000,1≤L≤2×1091\le L\le2\times10^9,0≤xi≤yi≤2×1090\le x_i\le y_i\le2\times10^9,0≤si≤2×1090\le s_i\le2\times10^9。按编号给出的位置单调不减。