← 返回题目列表

AtCoder · abc414_g

G. AtCoder快车4

中文机器翻译题面 查看原题

分数: 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 如下:

  1. 登上 1st特快列车到站 1 站下车 6。票价是 c_1+|x_1-x_6|=100+|0-150|=250.
  2. 登上 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