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

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 :

polylogK / テスター :

lumc_

5 ProblemId : 2068 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-01-05 22:29:29

問題文

新年早々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} \dots T_{N - 1}$ 
 $M$ 
 $L_{1} R_{1} D_{1}$ 
 $L_{2} R_{2} D_{2}$ 
 $⋮$ 
 $L_{M - 1} R_{M - 1} D_{M - 1}$ 
 $L_{M} R_{M} D_{M}$

1行目に駅の個数 $N (2 \leq N \leq 10^{5})$ が与えられます.
2行目に $N - 1$ 個の駅の始発電車の時刻 $T_{i} (0 \leq T_{i} \leq 10^{9})$ が整数で与えられます.
3行目に電車遅延の回数 $M (1 \leq M \leq 10^{5})$ が与えられます.
4行目から4+M行目までに電車遅延の範囲 $L_{i}, R_{i} (1 \leq L_{i} \leq R_{i} < N)$ と遅延時間 $D_{i} (1 \leq D_{i} \leq 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

出力

まず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

出力

出力が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

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

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

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力