102927: [Atcoder]ABC292 Ex - Rating Estimator
Description
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 $i$ 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 1
5 6 7 5 1 9 3 8 4 9 2 10 1 0 3 0 3 30 5 100 1 100
Sample Output 1
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.
Input
题意翻译
你要参加 $n$ 场比赛。 如果第 $i$ 场比赛你的成绩为 $p_i$,那你的 rating 在第 $k$ 场比赛后将会变为前 $k$ 场比赛成绩的平均值,也就是$\frac{1}{k}(\sum^{k}_{i=1}p_i)$。 不过,如果在某场比赛后,你的 rating 大于等于一个值 $B$,它以后将不会在变化。 你对你每场比赛的成绩做了估计,你估计第 $i$ 场比赛你的成绩为 $a_i$。 现在有 $q$ 组询问,每组询问中给出两个数 $c$ 和 $x$,表示将第 $c$ 场比赛的成绩修改为 $x$(注意这一操作在此后的询问中会被保留),输出修改之后,如果你每场比赛的真实成绩都与预估的一样,你在第 $n$ 场比赛后的 rating。Output
问题描述
您将参加编号为1到N的N个比赛,按时间顺序编号。
每场比赛的参赛者将获得该场比赛的称为“表现”的值。设P_i为第i场比赛的表现。
此外,您有一个称为“评级”的值,它会根据比赛中的表现而变化。初始评级为0,比赛n后的评级为$\frac{1}{n} \left(\sum_{i=1}^n P_i \right)$。
但是,一旦您的评级达到或高于B,后续比赛将不会影响您的评级。
在比赛开始前,您已经决定对每场比赛的表现进行预估。设$a_i$为第i场比赛的初始表现预估。按照给定的顺序处理Q个查询。
在每个查询中,您将获得两个整数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}$,则认为您的输出是正确的。
样例输入1
5 6 7 5 1 9 3 8 4 9 2 10 1 0 3 0 3 30 5 100 1 100
样例输出1
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)$。
第一个查询将$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,应在第一行打印。