← 返回题目列表

Codeforces · 939/E

E. 最大化!

中文机器翻译题面 查看原题

给定一个由正整数组成的多重集 S(最初为空)。有两种查询:

1. 在S中添加一个正整数,新添加的整数不小于其中的任何数字。
2. 找到集合 S 的子集 s,使得值 $$\max(s) - \mathrm{mean}(s)$$ 为最大可能值。这里 max(s) 表示 s 中元素的最大值,$$\operatorname{mean}(s)$$ — s 中数字的平均值。输出 $$\max(s) - \mathrm{mean}(s)$$ 的最大可能值。

输入

第一行包含一个整数 Q (1 ≤ Q ≤ 5·105) — 查询数。

接下来的 Q 行中的每一行都包含查询的描述。对于类型 1 的查询,给出两个整数 1 和 x,其中 x (1 ≤ x ≤ 109) 是应添加到 S 中的数字。保证 x 不小于 S 中的任何数字。对于类型 2 的查询,给出单个整数 2。

保证第一个查询的类型为 1,i。 e.当类型2的查询到来时,S不为空。

输出

按照输入中给出的顺序输出第二类型的每个查询的答案。每个数字应打印在单独的行中。

如果您的每个答案的绝对或相对误差不大于 10 - 6,则您的答案被视为正确。

正式来说,让你的答案是a,陪审团的答案是b。如果 $${ \frac { | 则认为您的答案是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$。

示例

输入 #1

6
1 3
2
1 4
2
1 8
2

输出 #1

0.0000000000
0.5000000000
3.0000000000

输入 #2

4
1 1
1 4
1 5
2

输出 #2

2.0000000000