E. Maximize!

Codeforces

IDCF939E

Time3000ms

Memory256MB

Difficulty—

binary searchgreedyternary searchtwo pointers

English · Original

Chinese · Translation

Formal · Original

You are given a multiset _S_ consisting of positive integers (initially empty). There are two kind of queries: 1. Add a positive integer to _S_, the newly added integer is not less than any number in it. 2. Find a subset _s_ of the set _S_ such that the value is maximum possible. Here _max_(_s_) means maximum value of elements in _s_, — the average value of numbers in _s_. Output this maximum possible value of . ## Input The first line contains a single integer _Q_ (1 ≤ _Q_ ≤ 5·105) — the number of queries. Each of the next _Q_ lines contains a description of query. For queries of type 1 two integers 1 and _x_ are given, where _x_ (1 ≤ _x_ ≤ 109) is a number that you should add to _S_. It's guaranteed that _x_ is not less than any number in _S_. For queries of type 2, a single integer 2 is given. It's guaranteed that the first query has type 1, i. e. _S_ is not empty when a query of type 2 comes. ## Output Output the answer for each query of the second type in the order these queries are given in input. Each number should be printed in separate line. Your answer is considered correct, if each of your answers has absolute or relative error not greater than 10 - 6. Formally, let your answer be _a_, and the jury's answer be _b_. Your answer is considered correct if . [samples]

你被给定一个多重集 #cf_span[S]，包含正整数（初始为空）。有两种类型的查询：第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 5·105]）——查询的数量。接下来的 #cf_span[Q] 行每行描述一个查询。对于类型为 #cf_span[1] 的查询，给出两个整数 #cf_span[1] 和 #cf_span[x]，其中 #cf_span[x]（#cf_span[1 ≤ x ≤ 109]）是你应添加到 #cf_span[S] 中的数。保证 #cf_span[x] 不小于 #cf_span[S] 中的任何数。对于类型为 #cf_span[2] 的查询，给出一个整数 #cf_span[2]。保证第一个查询是类型 #cf_span[1]，即当类型为 #cf_span[2] 的查询出现时，#cf_span[S] 非空。请按输入中给出的顺序，为每个第二类查询输出答案。每个数应单独占一行。你的答案被认为是正确的，当且仅当每个答案的绝对误差或相对误差不超过 #cf_span[10 - 6]。形式上，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]。你的答案被认为是正确的，如果。 ## Input 第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 5·105]）——查询的数量。接下来的 #cf_span[Q] 行每行描述一个查询。对于类型为 #cf_span[1] 的查询，给出两个整数 #cf_span[1] 和 #cf_span[x]，其中 #cf_span[x]（#cf_span[1 ≤ x ≤ 109]）是你应添加到 #cf_span[S] 中的数。保证 #cf_span[x] 不小于 #cf_span[S] 中的任何数。对于类型为 #cf_span[2] 的查询，给出一个整数 #cf_span[2]。保证第一个查询是类型 #cf_span[1]，即当类型为 #cf_span[2] 的查询出现时，#cf_span[S] 非空。 ## Output 请按输入中给出的顺序，为每个第二类查询输出答案。每个数应单独占一行。你的答案被认为是正确的，当且仅当每个答案的绝对误差或相对误差不超过 #cf_span[10 - 6]。形式上，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]。你的答案被认为是正确的，如果。 [samples]

**Definitions** Let $ Q \in \mathbb{Z}^+ $ be the number of queries. Let $ S \subseteq \mathbb{Z}^+ $ be a multiset, initially empty. For each query $ i \in \{1, \dots, Q\} $: - If type 1: $ (1, x_i) $, add $ x_i $ to $ S $, where $ x_i \geq \max(S) $ before insertion. - If type 2: $ (2) $, compute and output the median of $ S $. **Constraints** 1. $ 1 \leq Q \leq 5 \cdot 10^5 $ 2. For each type-1 query: $ 1 \leq x_i \leq 10^9 $ and $ x_i \geq \max(S) $ at time of insertion. 3. Type-2 queries occur only when $ S \neq \emptyset $. **Objective** For each type-2 query, output the median of the multiset $ S $. Let $ n = |S| $. The median is: - If $ n $ is odd: the middle element when $ S $ is sorted. - If $ n $ is even: the average of the two middle elements when $ S $ is sorted. That is, let $ S_{\text{sorted}} = (s_1 \leq s_2 \leq \dots \leq s_n) $. Then: $$ \text{median} = \begin{cases} s_{(n+1)/2} & \text{if } n \text{ is odd}, \\ \frac{s_{n/2} + s_{n/2 + 1}}{2} & \text{if } n \text{ is even}. \end{cases} $$

Samples

Input #1

Output #1

0.0000000000
0.5000000000
3.0000000000

Input #2

Output #2

2.0000000000

API Response (JSON)

{
  "problem": {
    "name": "E. Maximize!",
    "description": {
      "content": "You are given a multiset _S_ consisting of positive integers (initially empty). There are two kind of queries: 1.  Add a positive integer to _S_, the newly added integer is not less than any number i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF939E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a multiset _S_ consisting of positive integers (initially empty). There are two kind of queries:\n\n1.  Add a positive integer to _S_, the newly added integer is not less than any number i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个多重集 #cf_span[S]，包含正整数（初始为空）。有两种类型的查询：\n\n第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 5·105]）——查询的数量。\n\n接下来的 #cf_span[Q] 行每行描述一个查询。对于类型为 #cf_span[1] 的查询，给出两个整数 #cf_span[1] 和 #cf_span[x]，其中 #cf_span[x]（#c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ S \\subseteq \\mathbb{Z}^+ $ be a multiset, initially empty.  \n\nFor each query $ i \\in \\{1, \\dots, Q\\} $:  \n- If type 1: $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments