Ex - Rating Estimator

Contest Duration: 2023-03-04(Sat) 12:00 - 2023-03-04(Sat) 13:40 (local time) (100 minutes) Back to Home

Ex - Rating Estimator Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

あなたは $N$ 個のコンテストに参加します。コンテストが開催される順にコンテスト $1$ , コンテスト $2$ , $\dots$ コンテスト $N$ と呼びます。
各コンテストに参加すると、コンテストごとに パフォーマンス という値が与えられます。コンテスト $i$ で与えられるパフォーマンスを $P_i$ とします。
また、あなたは レーティング という値を持っています。レーティングはコンテストでのパフォーマンスによって変化する値です。コンテストに参加する前のレーティングの値は $0$ で、コンテスト $n$ に出た後のレーティングの値は $\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$ に変化します。
ただし、あなたのレーティングが一度 $B$ 以上になると、それ以降はコンテストに参加してもレーティングは変動しなくなります。

あなたはコンテストに出る前に、それぞれのコンテストで得られるパフォーマンスを予測することにしました。はじめ、コンテスト $i$ のパフォーマンスの予測値を $a_i$ とします。クエリが $Q$ 個与えられるので入力される順にすべて処理してください。

各クエリでは 2 個の整数 $c, x$ が与えられます。あなたは、まずコンテスト $c$ のパフォーマンスの予測値を $x$ に変更します。(この変更は永続的です。) そして、あなたが $N$ 個のコンテスト全てで現在の予測値通りのパフォーマンスを得られた場合の、全てのコンテストに参加した後のレーティングの値を答えてください。

制約

$1 \leq N \leq 5 \times 10^5$
$1 \leq B \leq 10^9$
$1 \leq Q \leq 10^5$
$0 \leq a_i \leq 10^9$
$1 \leq c \leq N$
$0 \leq x \leq 10^9$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、 $c_i, x_i$ は $i$ 番目のクエリで与えられる $c, x$ を意味する。

 $N$   $B$   $Q$ 
 $a_1$   $a_2$   $\dots$   $a_N$ 
 $c_1$   $x_1$ 
 $c_2$   $x_2$ 
 $\vdots$ 
 $c_Q$   $x_Q$

出力

$Q$ 行出力せよ。 $i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が $10^{-9}$ 以下であれば正解として扱われる。

入力例 1Copy

Copy

出力例 1Copy

Copy

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

はじめ、 $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8)$ です。
1 番目のクエリによって $a_4$ が $9$ に変更されて $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8)$ となります。
このとき、コンテスト $i$ でパフォーマンス $a_i$ を取った場合のあなたのレーティングの推移は次の通りです。

はじめ、レーティングは $0$ です。
コンテスト $1$ が終了した時点でレーティングは $5 / 1 = 5$ に変化します。
コンテスト $2$ が終了した時点でレーティングは $(5 + 1) / 2 = 3$ に変化します。
コンテスト $3$ が終了した時点でレーティングは $(5 + 1 + 9) / 3 = 5$ に変化します。
コンテスト $4$ が終了した時点でレーティングは $(5 + 1 + 9 + 9) / 4 = 6$ に変化します。
以降、レーティングの値は変化しません。なぜならば、 $4$ 番目のコンテストが終了した時点でレーティングが $B$ 以上の値になっているからです。

よって、全てのコンテストが終了した時点でのレーティングは $6$ なので、1 行目にはこれを出力します。

Score : $600$ points

Problem Statement

You will participate in $N$ contests, numbered $1$ to $N$ in chronological order.
A participant in each contest will be given a value called performance for that contest. Let $P_i$ be the performance for contest $i$ .
Additionally, you have a value called rating, which changes according to the performances in contests. The initial rating is $0$ , and the rating after contest $n$ is $\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$ .
However, once your rating is $B$ or higher, later contests will not affect your rating.

Before the contests, you have decided to estimate your performance in each contest. Let $a_i$ be the initial estimate of your performance in contest $i$ . Process $Q$ queries in the order they are given.

In each query, you are given two integers $c$ and $x$ . First, change the estimate of your performance in contest $c$ to $x$ . (This change is persistent.) Then, assuming that you get the estimated performances in all $N$ contests, print your final rating after the contests.

Constraints

$1 \leq N \leq 5 \times 10^5$
$1 \leq B \leq 10^9$
$1 \leq Q \leq 10^5$
$0 \leq a_i \leq 10^9$
$1 \leq c \leq N$
$0 \leq x \leq 10^9$
All values in the input are integers.

Input

The input is given from Standard Input in the following format, where $c_i$ and $x_i$ are the $c$ and $x$ for the $i$ -th query:

 $N$   $B$   $Q$ 
 $a_1$   $a_2$   $\dots$   $a_N$ 
 $c_1$   $x_1$ 
 $c_2$   $x_2$ 
 $\vdots$ 
 $c_Q$   $x_Q$

Output

Print $Q$ lines. The $i$ -th line should contain the answer to the $i$ -th query.
Your output is considered correct if the absolute or relative error from the true answer is at most $10^{-9}$ .

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

Initially, $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8)$ .
The first query changes $a_4$ to $9$ , making $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8)$ .
Here, assuming that your performance in contest $i$ is $a_i$ , your rating will change as follows.

Initially, your rating is $0$ .
After contest $1$ , your rating will be $5 / 1 = 5$ .
After contest $2$ , your rating will be $(5 + 1) / 2 = 3$ .
After contest $3$ , your rating will be $(5 + 1 + 9) / 3 = 5$ .
After contest $4$ , your rating will be $(5 + 1 + 9 + 9) / 4 = 6$ .
Your rating will no longer change, because your rating after contest $4$ is not less than $B$ .

Thus, your final rating after the contests is $6$ , which should be printed in the first line.