bzoj#P1171. 大sz的游戏
大sz的游戏
题目描述
大 sz 最近在玩一个由星球大战改编的游戏。话说绝地武士当前共控制了 个星球。但是,西斯正在暗处悄悄地准备他们的复仇计划。绝地评议会也感觉到了这件事。于是,准备加派绝地武士到各星球防止西斯的突袭。一个星球受到攻击以后,会尽快通知到总基地。需要的时间越长的星球就需要越多绝地武士来防御。为了合理分配有限的武士,大 sz 需要你帮他求出每个星球各需要多少时间能够通知到总基地。由于某种原因, 个星球排成一条直线,编号 至 。其中总基地建在 号星球上。每个星球虽然都是绝地武士控制的,但是上面居住的生物不一定相同,并且科技水平也不一样。第 个星球能收到并分析波长在 之间的信号,并且也能够发出在这个区间的信号,但是不能发出其他任何波长的信号。由于技术原因,每个星球只能发信号到比自己编号小的距离不超过 的星球。特别地,强大的总基地可以接收任何波长的信号。每个星球处理接收到的数据需要 个单位时间,传输时间可以忽略不计。
输入格式
第一行两个正整数 。接下来 行,总共第 行包含了三个正整数 ,其中 表示第 个星球距离 号星球 的距离, 严格递增。
输出格式
总共 行,每行一个数分别表示 到 号星球至少需要多少单位时间,总基地能够处理好数据,如果无法传到总基地则输出 。
3 1
1 2 1
2 3 2
1
2
3 3
1 2 1
2 3 2
1
1
数据规模与约定
对于 的数据,;
对于 的数据, $2 \le n \le 2.5 \times 10^5, 0 \le x_i,y_i,l_i \le 2\times 10^9, 1 \le l \le 2\times 10^9, x_i \le y_i$。
题目来源
By 俞华程