No.631 Noel-chan and the Train Trip
Problem Statement
Right at the start of the new year, Noel-chan felt like going on a trip by train.
Kirimiko Town has N stations. From $駅_i$, at minute $T_i$ and every 1 minute after that, a train departs for $駅_{i+1}$, taking 3 minutes to get there.
However, since it is the start of the new year, train delays occur from time to time. When a train delay occurs, the first trains from $駅_{L_i}$ to $駅_{R_i}$ are delayed by $D_i$ minutes.
Noel-chan is initially at station 1. Each time a train delay occurs, find the minimum time for Noel-chan to arrive at station $N$.
The current time is $0$.
Input
$N$
$T_1\ T_2\ \cdots \ T_{N-1}$
$M$
$L_1\ R_1\ D_1$
$L_2\ R_2\ D_2$
$\vdots$
$L_{M-1}\ R_{M-1}\ D_{M-1}$
$L_M\ R_M\ D_M$
Line 1 contains the number of stations $N(2\le N\le 10^5)$.
Line 2 contains the first-train times $T_i(0\le T_i\le 10^9)$ of the $N-1$ stations as integers.
Line 3 contains the number of train delays $M(1\le M\le 10^5)$.
Lines 4 through 3+M contain the range of each train delay $L_i, R_i(1\le L_i\le R_i< N)$ and the delay time $D_i(1\le D_i\le 10^9)$ as integers.
Output
Output M lines. On each line, print as an integer the time Noel-chan needs after the corresponding train delay has occurred, followed by a newline.
Sample
Sample 1
Input
10 0 1 2 3 4 5 6 7 8 5 1 1 5 2 3 7 5 8 5 6 9 7 1 9 7
Output
32 32 32 32 39
First, the 1st train delay makes the first train at station 1 late by 5 minutes. The minimum time to $駅_N$ at this point is 32 minutes.
The 2nd train delay makes the first trains at stations 2 to 3 late by 7 minutes. The minimum time to $駅_N$ at this point is 32 minutes.
The 3rd train delay makes the first trains at stations 5 to 8 late by 5 minutes. The minimum time to $駅_N$ at this point is 32 minutes.
The 4th train delay makes the first trains at stations 6 to 9 late by 7 minutes. The minimum time to $駅_N$ at this point is 32 minutes.
The 5th train delay makes the first trains at stations 1 to 9 late by 7 minutes. The minimum time to $駅_N$ at this point is 39 minutes.
Sample 2
Input
10 0 1 2 3 4 5 6 7 8 5 1 9 1000000000 1 9 1000000000 1 9 1000000000 1 9 1000000000 1 9 1000000000
Output
1000000027 2000000027 3000000027 4000000027 5000000027
The output may not fit in a 32bit integer.
Sample 3
Input
10 0 76 78 64 100 95 10 98 46 5 5 6 61 9 9 38 8 8 28 1 9 87 4 4 66
Output
176 176 176 263 263
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
lumc_