D. Sum of Medians

Codeforces

IDCF85D

Time3000ms

Memory256MB

Difficulty—

binary searchbrute forcedata structuresimplementation

English · Original

Chinese · Translation

Formal · Original

In one well-known algorithm of finding the _k_\-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it's the third largest element for a group of five). To increase the algorithm's performance speed on a modern video card, you should be able to find a sum of medians in each five of the array. A _sum of medians_ of a sorted _k_\-element set _S_ = {_a_1, _a_2, ..., _a__k_}, where _a_1 < _a_2 < _a_3 < ... < _a__k_, will be understood by as The operator stands for taking the remainder, that is stands for the remainder of dividing _x_ by _y_. To organize exercise testing quickly calculating _the sum of medians_ for a changing set was needed. ## Input The first line contains number _n_ (1 ≤ _n_ ≤ 105), the number of operations performed. Then each of _n_ lines contains the description of one of the three operations: * _add _x__ — add the element _x_ to the set; * _del _x__ — delete the element _x_ from the set; * _sum_ — find the _sum of medians_ of the set. For any _add _x__ operation it is true that the element _x_ is not included in the set directly before the operation. For any _del _x__ operation it is true that the element _x_ is included in the set directly before the operation. All the numbers in the input are positive integers, not exceeding 109. ## Output For each operation _sum_ print on the single line _the sum of medians_ of the current set. If the set is empty, print 0. Please, do not use the _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use the _cin_, _cout_ streams (also you may use the _%I64d_ specificator). [samples]

在一种著名的寻找第 #cf_span[k] 小元素的算法中，我们需要将所有元素划分为每五个连续元素一组，并求出每组的中位数。中位数是指排序后数组的中间元素（对于五个元素的组，它是第三大的元素）。为了提高该算法在现代显卡上的运行速度，你需要能够快速计算出数组中每五个元素的中位数之和。对于一个已排序的 #cf_span[k] 元素集合 #cf_span[S = {a1, a2, ..., ak}]，其中 #cf_span[a1 < a2 < a3 < ... < ak]，其 _中位数之和_ 定义为：其中操作符表示取余，即表示 #cf_span[x] 除以 #cf_span[y] 的余数。为了快速进行练习测试，需要能够高效计算动态变化集合的 _中位数之和_。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示执行的操作数量。接下来的 #cf_span[n] 行，每行描述以下三种操作之一：对于任何 _add #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前不在集合中。对于任何 _del #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前在集合中。输入中的所有数字均为不超过 #cf_span[10^9] 的正整数。对于每个 _sum_ 操作，请在单独一行输出当前集合的 _中位数之和_。如果集合为空，请输出 0。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示执行的操作数量。接下来的 #cf_span[n] 行，每行描述以下三种操作之一： _add #cf_span[x]_ — 将元素 #cf_span[x] 加入集合； _del #cf_span[x]_ — 将元素 #cf_span[x] 从集合中删除； _sum_ — 计算集合的 _中位数之和_。对于任何 _add #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前不在集合中。对于任何 _del #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前在集合中。输入中的所有数字均为不超过 #cf_span[10^9] 的正整数。 ## Output 对于每个 _sum_ 操作，请在单独一行输出当前集合的 _中位数之和_。如果集合为空，请输出 0。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。 [samples]

**Definitions** Let $ S \subseteq \mathbb{Z}^+ $ be a dynamic multiset (initially empty). Let $ |S| = k $, and let $ S = \{a_1, a_2, \dots, a_k\} $ with $ a_1 < a_2 < \dots < a_k $ be the sorted representation of $ S $. For a sorted set $ S $ of size $ k $, the **sum of medians** is defined as: $$ \sum_{i=1}^{\left\lceil \frac{k}{5} \right\rceil} a_{5(i-1) + 3} $$ where the $ i $-th group of five consists of elements at positions $ 5(i-1)+1 $ to $ 5(i-1)+5 $, and the median of each group is the 3rd element (i.e., index $ 5(i-1)+3 $) in the sorted group. If a group has fewer than 5 elements, it is still considered, and its median is the element at position $ \min(3, \text{group size}) $ within the group (i.e., the 3rd element if it exists, otherwise the last). **Operations** Given $ n \in \mathbb{Z} $, $ 1 \le n \le 10^5 $, perform $ n $ operations on $ S $: - `add x`: Insert $ x \in \mathbb{Z}^+ $, $ x \le 10^9 $, into $ S $ (guaranteed not present). - `del x`: Remove $ x \in \mathbb{Z}^+ $, $ x \le 10^9 $, from $ S $ (guaranteed present). - `sum`: Compute and output the **sum of medians** of the current $ S $; if $ S = \emptyset $, output 0. **Objective** For each `sum` operation, output the sum of medians of the current sorted set $ S $, computed as described.

Samples

Input #1

6
add 4
add 5
add 1
add 2
add 3
sum

Output #1

Input #2

14
add 1
add 7
add 2
add 5
sum
add 6
add 8
add 9
add 3
add 4
add 10
sum
del 1
sum

Output #2

5
11
13

API Response (JSON)

{
  "problem": {
    "name": "D. Sum of Medians",
    "description": {
      "content": "In one well-known algorithm of finding the _k_\\-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the midd",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF85D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In one well-known algorithm of finding the _k_\\-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the midd...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在一种著名的寻找第 #cf_span[k] 小元素的算法中，我们需要将所有元素划分为每五个连续元素一组，并求出每组的中位数。中位数是指排序后数组的中间元素（对于五个元素的组，它是第三大的元素）。为了提高该算法在现代显卡上的运行速度，你需要能够快速计算出数组中每五个元素的中位数之和。\n\n对于一个已排序的 #cf_span[k] 元素集合 #cf_span[S = {a1, a2, ..., ak}]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\subseteq \\mathbb{Z}^+ $ be a dynamic multiset (initially empty).  \nLet $ |S| = k $, and let $ S = \\{a_1, a_2, \\dots, a_k\\} $ with $ a_1 < a_2 < \\dots < a_k $ be the sorted r...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments