分数: 625 点
问题陈述
在AtCoder王国,有一条东西向延伸的铁路线,这条线有车站 1,2,\ldots,N。车站 i\ (1\leq i\leq N) 位于坐标 x_i (x_1 < x_2 < \ldots < x_N).
在此线路上,AtCoder Express 公司运营 M 特快列车的类型。
的 i特快列车的运行情况如下:
- 您可以在其中一个车站登上这趟列车 l_i,l_i+1,\ldots,r_i.
- 您可以在其中一个车站下车 L_i, L_i+1, \ldots, R_i。在这里,火车单向行驶,或东或西,满足 r_i\lt L_i or R_i\lt l_i.
- 票价包括基本票价 c_i 加上根据从上车车站到目的地车站的距离计算的金额。具体来说,从车站出发时 s\ (l_i\leq s\leq r_i) 到车站 t\ (L_i\leq t\leq R_i),票价为 c_i+|x_s-x_t|.
您目前在车站 1。对于每个 k\ (2\leq k\leq N),判断是否可以从车站出发 1 到车站 k 通过在特快列车之间换乘,如果您可以旅行,请查找旅行所需的最低总票价。
约束
- 2\leq N\leq 10^5
- 1\leq M\leq 10^5
- 0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12}
- 1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N
- r_i\lt L_i or R_i\lt l_i.
- 1\leq c_i\leq 10^{12}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M x_1 x_2 \ldots x_N l_1 r_1 L_1 R_1 c_1 l_2 r_2 L_2 R_2 c_2 \vdots l_M r_M L_M R_M c_M
输出
按以下格式输出答案:
\mathrm{ans}_2 \mathrm{ans}_3 \ldots \mathrm{ans}_N
\mathrm{ans}_i 是以下问题的答案 k=i。如果您可以从车站出发 1 到车站 i, \mathrm{ans}_i 是旅行所需的最低总票价;否则, \mathrm{ans}_i is -1.
示例输入 1
6 3 0 20 50 90 110 150 1 2 5 6 100 1 1 2 3 10000 6 6 1 2 30
示例输出 1
410 10050 -1 210 250
您可以前往车站 2 如下:
- 登上 1st特快列车到站 1 站下车 6。票价是 c_1+|x_1-x_6|=100+|0-150|=250.
- 登上 3rd 特快列车到站 6 站下车 2。票价是 c_3+|x_6-x_2|=30+|150-20|=160.
本例中的总票价为 410,这是最小值。
您无法前往车站 4.
示例输入 2
10 5 4427 6839 17992 39701 46954 76602 81804 91814 95651 95895 3 4 10 10 60978 1 1 4 4 30037 9 10 7 8 66643 4 4 1 2 50872 8 10 3 7 23949
示例输出 2
149045 284335 65311 255373 225725 220523 253207 -1 182483