No.631 Noelちゃんと電車旅行

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 54
作問者 : NoelちゃんNoelちゃん / テスター : lumc_lumc_
4 ProblemId : 2068 / 出題時の順位表

問題文

新年早々Noelちゃんは電車で旅行に出かけたくなりました.
霧弥湖町にはN個の駅があります, $駅_i$からは$T_i$分以降1分ごとに$駅_{i+1}$まで3分で向かう電車が出ています.
ただし新年早々ゆえに電車遅延が時々発生します, 電車遅延が起こると$駅_{L_i}$から$駅_{R_i}$までの始発電車が$D_i$分遅れます.
Noelちゃんは初め駅1にいます, 電車遅延が起こるたびにNoelちゃんが駅$N$に着く最短時間を求めてください.

現在時刻は$0$とします。

入力

$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$

1行目に駅の個数$N(2\le N\le 10^5)$が与えられます.
2行目に$N-1$個の駅の始発電車の時刻$T_i(0\le T_i\le 10^9)$が整数で与えられます.
3行目に電車遅延の回数$M(1\le M\le 10^5)$が与えられます.
4行目から4+M行目までに電車遅延の範囲$L_i, R_i(1\le L_i\le R_i< N)$と遅延時間$D_i(1\le D_i\le 10^9)$が整数で与えられます.

出力

M行の出力があります, 各行には対応する電車遅延発生後のNoelちゃんの必要時間を整数で改行付きで出力してください.

サンプル

サンプル1
入力
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
出力
32
32
32
32
39

まず1回目の電車遅延により駅1の始発が5分遅れます, この時の$駅_N$までの最短時間は32分です.
2回目の電車遅延により駅2から駅3の始発が7分遅れます, この時の$駅_N$までの最短時間は32分です.
3回目の電車遅延により駅5から駅8の始発が5分遅れます, この時の$駅_N$までの最短時間は32分です.
4回目の電車遅延により駅6から駅9の始発が7分遅れます, この時の$駅_N$までの最短時間は32分です.
5回目の電車遅延により駅1から駅9の始発が7分遅れます, この時の$駅_N$までの最短時間は39分です.

サンプル2
入力
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
出力
1000000027
2000000027
3000000027
4000000027
5000000027

出力が32bit整数に収まらないこともあります.

サンプル3
入力
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
出力
176
176
176
263
263

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。