外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

R - NyanCoder Munchkin Contest

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 500 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

プログラミングコンテストサイト「nyancoder」では、「nyancoder munchkin contest(NMC)」が定期的に開催されています。 わりとねこくんは、これまでに開催された NN 回の NMC すべてに参加しました。第 ii 回のコンテストでのパフォーマンスの初期値は PiP_i です。

NMC にはいぬが参加することがあります。NMC は only-cat なので、参加者がいぬであると判明すると、その参加者は BAN されます。それに伴い、わりとねこくんのパフォーマンスが、ある回以降のすべての NMC で同じ量だけ加算されます。

QQ 個のクエリが与えられます。ii 番目のクエリでは整数 ki,xi,li,rik_i, x_i, l_i, r_i が与えられるので、次の 2 つの処理を順に行ってください。

  1. kik_i 回目から NN 回目までの各コンテストのパフォーマンスに xix_i を加えます。すなわち、ki≤j≤Nk_i \le j \le N を満たすすべての jj について、PjP_j を Pj+xiP_j+x_i に更新します。xix_i は 00 のこともあります。更新後の値は以降のクエリに引き継がれます。
  2. 更新後のパフォーマンスを使い、わりとねこくんが lil_i 回目から rir_i 回目までのコンテストにだけ順に参加したと仮定したときの、rir_i 回目の終了時点のレートを求めます。

レートの計算方法

第 ll 回から第 rr 回までのコンテストに順に参加するとき、第 ii 回終了時点のレートを RiR_i とします。

  • 最初に参加する第 ll 回の終了時点では、Rl=PlR_l=P_l です。
  • 第 l+1l+1 回から第 rr 回までは、次の式で順にレートを計算します。計算途中で整数への丸めは行いません。

Ri=Ri−1+Pi−Ri−120R_i=R_{i-1}+\frac{P_i-R_{i-1}}{20}

制約

  • 1≤N,Q≤1051 \le N,Q \le 10^5
  • 1≤Pi≤1051 \le P_i \le 10^5 (1≤i≤N)(1 \le i \le N)
  • 1≤ki≤N1 \le k_i \le N (1≤i≤Q)(1 \le i \le Q)
  • 0≤xi≤1050 \le x_i \le 10^5 (1≤i≤Q)(1 \le i \le Q)
  • 1≤li≤ri≤N1 \le l_i \le r_i \le N (1≤i≤Q)(1 \le i \le Q)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

NQN \quad Q P1P2⋯PNP_1 \quad P_2 \quad \cdots \quad P_N k1x1l1r1k_1 \quad x_1 \quad l_1 \quad r_1 k2x2l2r2k_2 \quad x_2 \quad l_2 \quad r_2 ⋮\vdots kQxQlQrQk_Q \quad x_Q \quad l_Q \quad r_Q

出力

QQ 行出力してください。ii 行目には、ii 番目のクエリで求めた第 rir_i 回終了時点のレートを出力してください。

正答との絶対誤差または相対誤差が 10−510^{-5} 以下であれば正解とみなされます。

入力例 1

3 3
100 200 300
2 20 1 3
3 0 2 3
1 10 3 3

出力例 1

116.7
225
330
  • 1 番目のクエリで、パフォーマンスは (100,220,320)(100,220,320) になります。レートは 100100、106106、116.7116.7 と推移します。
  • 2 番目のクエリでは 00 を加えるので、パフォーマンスは (100,220,320)(100,220,320) のままです。第 2 回が初参加なので、レートは 220220 から始まり、第 3 回終了時点で 220+(320−220)/20=225220+(320-220)/20=225 になります。
  • 3 番目のクエリで、パフォーマンスは (110,230,330)(110,230,330) になります。第 3 回だけに参加するので、答えは 330330 です。

入力例 2

1 3
5
1 0 1 1
1 100000 1 1
1 1 1 1

出力例 2

5
100005
100006

コンテストは 1 回だけなので、各クエリへの答えは更新後の P1P_1 そのものです。

入力例 3

4 3
10 20 30 40
4 100 1 2
2 10 3 4
3 20 3 4

出力例 3

10.5
45.5
65.5

1 番目のクエリの更新位置は、このクエリの参加区間より後ろにあります。この更新で第 4 回のパフォーマンスは 140140 になり、2 番目のクエリではさらに 1010 が加わった 150150 を使います。

誤差ジャッジ:絶対誤差または相対誤差が10-5以下なら正解です。

参加受付は終了しました。