/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 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 または 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 または 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 まで移動できる場合は移動に必要な運賃の合計の最小値を、移動できない場合は -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 種類目の特急列車に駅 1 から乗車して駅 6 で降車する。運賃は c_1+|x_1-x_6|=100+|0-150|=250 である。
- 3 種類目の特急列車に駅 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
Score : 625 points
Problem Statement
In AtCoder Kingdom, there is a railway line extending east-west, and this line has stations 1,2,\ldots,N. Station i\ (1\leq i\leq N) is located at coordinate x_i (x_1 < x_2 < \ldots < x_N).
On this line, AtCoder Express company operates M types of express trains.
The i-th type of express train operates as follows:
- You can board this train at one of the stations l_i,l_i+1,\ldots,r_i.
- You can get off this train at one of the stations L_i, L_i+1, \ldots, R_i. Here, the train travels in one direction, either east or west, satisfying r_i\lt L_i or R_i\lt l_i.
- The fare consists of a base fare of c_i plus an amount based on the distance from the boarding station to the destination station. Specifically, when traveling from station s\ (l_i\leq s\leq r_i) to station t\ (L_i\leq t\leq R_i), the fare is c_i+|x_s-x_t|.
You are currently at station 1. For each k\ (2\leq k\leq N), determine whether you can travel from station 1 to station k by transferring between express trains, and if you can travel, find the minimum total fare required for the travel.
Constraints
- 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}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Output the answer in the following format:
\mathrm{ans}_2 \mathrm{ans}_3 \ldots \mathrm{ans}_N
\mathrm{ans}_i is the answer for k=i. If you can travel from station 1 to station i, \mathrm{ans}_i is the minimum total fare required for the travel; otherwise, \mathrm{ans}_i is -1.
Sample Input 1
6 3 0 20 50 90 110 150 1 2 5 6 100 1 1 2 3 10000 6 6 1 2 30
Sample Output 1
410 10050 -1 210 250
You can travel to station 2 as follows:
- Board the 1st express train at station 1 and get off at station 6. The fare is c_1+|x_1-x_6|=100+|0-150|=250.
- Board the 3rd express train at station 6 and get off at station 2. The fare is c_3+|x_6-x_2|=30+|150-20|=160.
The total fare in this case is 410, which is the minimum.
You cannot travel to station 4.
Sample Input 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
Sample Output 2
149045 284335 65311 255373 225725 220523 253207 -1 182483