問題一覧 > 通常問題

No.1950 片道きゃっちぼーる

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 96
作問者 : 👑 H20H20 / テスター : 👑 nullnull 蜜蜂蜜蜂
6 ProblemId : 7891 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-21 00:42:17

問題文

直線上に $N$ 人が一列に並んでいます。

左から $i$ 番目の人は位置 $X_i$ にいて、左右にちょうど $A_i$ の距離、ノーバウンドでボールを投げられます。

$N$ 人はそれぞれの定位置から動かずにボールを投げ、ボールが地面に落ちるまでの距離を測ります。

右側へ飛んだ距離を正とし、左側に飛んだ距離を負とします。出来る限り正の遠い距離にボールを投げたいです。

ルールを曲解した $N$ 人は、ボールの落下位置に人がいればキャッチしてもらい、その位置の人にまた投げてもらうことで距離を伸ばすことにしました。

曲解したルールで、$N$ 人はそれぞれ最大どのくらい遠い距離に投げられるか、$i$ 番目の位置からの正の方向への最大距離で答えてください。

入力

$N$
$X_1$ $X_2$ $\ldots$ $X_N$
$A_1$ $A_2$ $\ldots$ $A_N$

制約

  • $ 1 \le N \le 2\times10^{5}$
  • $ 0 \le X_i \le 10^{9}$
  • $X_1 \lt X_2 \lt \ldots \lt X_N$
  • $ 1 \le A_i \le 10^{9}$
  • 入力は全て整数

出力

$N$ 行出力してください。

$i$ 行目には、左から $i$ 番目の人の最大距離を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
0 2 3 4
2 9 5 2
出力
11
9
5
7

$1$ 番目と $4$ 番目の人は落下位置にいる $2$ 番目の人に投げてもらうことで距離を伸ばすことが出来ました。

サンプル2
入力
7
3 14 15 92 653 5897 9323
10 10 10 10 10 10 10
出力
10
10
10
10
10
10
10

落下位置には誰もいませんでした。

サンプル3
入力
10
0 5 7 10 15 20 25 30 35 40 
5 5 8 20 10 20 25 10 40 10
出力
50
45
43
40
35
30
25
20
40
10

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