問題一覧 > 通常問題

No.865 24時間降水量

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 155
作問者 : e869120e869120 / テスター : butsurizukibutsurizuki
2 ProblemId : 3316 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-08-16 14:41:46

問題文

E869120 君は、yuki 市の $N$ 時間分の降水量のデータを知っています。
最初、$i$ ($1 \leq i \leq N$) 時間目 (データが始まってから $i-1$ 時間後から $i$ 時間後の間) の降水量は $A_i$ ミリでした。

彼は $N$ 時間分のデータの中における、連続する $24$ 時間の降水量の最大値を計算しようとしました。

しかし、データの解析に進むにつれて、$Q$ 回に渡ってデータの変更が行われます。

  • $j$ ($1 \leq j \leq Q$) 回目の変更では、$T_j$ 時間目の降水量が $V_j$ ミリに変更されます。
  • ただし、どの変更においても、データの変更によってその時間の降水量が減る事はありません。

各変更の後について、$24$ 時間降水量の最大値を出力してください。

出力

全ての入力データは以下の制約を満たします。

  • $N$ は $24$ 以上 $200 \ 000$ 以下の整数
  • $Q$ は $1$ 以上 $200 \ 000$ 以下の整数
  • $T_j$ は $1$ 以上 $N$ 以下の整数
  • $A_i$ は $0$ 以上 $153$ 以下の整数
  • $V_j$ は $0$ 以上 $153$ 以下の整数
  • 変更によって降水量が減ることはない

入力

$N$
$A_1$ $A_2$ $A_3$ ... $A_N$
$Q$
$T_1$ $V_1$
$T_2$ $V_2$
$T_3$ $V_3$
...
$T_Q$ $V_Q$

出力

$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目の変更直後における連続する $24$ 時間降水量の最大値を求めてください。

サンプル

サンプル1
入力
25
0 0 0 0 2 3 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 2 5 13
2
1 0
1 80
出力
27
94

$2$ 回目の変更直後の降水量は、$[80, 0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 2, 5, 13]$ となります。その時、

  • 開始 $0$ 時間から $24$ 時間にかけての $24$ 時間降水量は $94$ ミリ
  • 開始 $1$ 時間から $25$ 時間にかけての $24$ 時間降水量は $27$ ミリ

よって、$24$ 時間降水量の最大値は $94$ となります。

サンプル2
入力
24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
24
1 153
2 153
3 153
4 153
5 153
6 153
7 153
8 153
9 153
10 153
11 153
12 153
13 153
14 153
15 153
16 153
17 153
18 153
19 153
20 153
21 153
22 153
23 153
24 153
出力
452
603
753
902
1050
1197
1343
1488
1632
1775
1917
2058
2198
2337
2475
2612
2748
2883
3017
3150
3282
3413
3543
3672

変更によって降水量が増えることも変わらないこともありますが、降水量が減ることがない事に注意してください。

サンプル3
入力
30
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10
5 0
8 0
11 0
3 0
24 0
25 0
16 0
17 0
4 0
19 0
出力
0
0
0
0
0
0
0
0
0
0

これがいつも通りみたいな yuki 国です。

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