#P2892. 强袭作战

    ID: 1999 传统题 1000ms 512MiB 尝试: 97 已通过: 58 难度: 8 上传者: 标签>CF2400提高+/省选-DAG 动态规划离散化普通线段树单调队列消除被支配候选

强袭作战

题目描述

nn 个点排成一行,依次从 11 到 nn 编号。除去 11 号点,每个点都有三个属性 li,ri,kil_i,r_i,k_i,满足 kik_i 单调递增。

若 2≤i<j≤n2\leq i< j\leq n 满足 kj−ki≤mk_j-k_i\leq m 且 [li,ri]∩[lj,rj]≠∅[l_i,r_i]\cap [l_j,r_j] \not = \varnothing,则存在一条 i→ji\to j,边权为 11 的边。

特殊的,若 ki≤mk_i\leq m,还存在一条 1→i1\to i,边权为 11 的边。

现在请你求出 11 号点到其它每个点的最短路。

输入格式

第一行两个整数 n,mn,m。

接下来 n−1n-1 行,每行三个非负整数 li,ri,kil_i,r_i,k_i 依次表示第 22 号点到第 nn 号点的属性。

输出格式

共 n−1n-1 行,第 ii 行一个整数表示到第 i+1i+1 号点的最短路,不能到达则输出 -1。

3 1
1 2 1
2 3 2
1
2

数据规模与约定

对于 30%30\% 的数据,1≤n≤2×1041\leq n\leq 2\times 10^4;

对于 100%100\% 的数据,1≤n≤2.5×1051\leq n\leq 2.5\times 10^5,0≤li,ri,ki≤2×1090\leq l_i,r_i,k_i\leq 2\times 10^9,1≤m≤2×1091\leq m\leq 2\times 10^9,li≤ril_i\leq r_i。