問題一覧 > 通常問題

No.631 Noel-chan and the Train Trip

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 99
作問者 : polylogK / テスター : lumc_
お気に入りにしたユーザー ProblemId : 2068 / 自分の提出
問題文最終更新日: 2026-10-17 09:35:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 179 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。