Remove Median Operations

AtCoder

IDarc210_b

Time3000ms

Memory256MB

Difficulty—

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$ and an integer sequence $B=(B_1,B_2,\ldots,B_M)$ of length $M$. Here, $N$ is **even**. You are given $Q$ queries. The $q$\-th query is given as a triple of integers $(t_q,i_q,x_q)$, and it does the following. * If $t_q=1$: In this case, $1\leq i_q\leq N$. This query changes $A_{i_q}$ to $x_q$. * If $t_q=2$: In this case, $1\leq i_q\leq M$. This query changes $B_{i_q}$ to $x_q$. After processing each query, find the answer to the following subproblem. > Initialize a multiset $X$ with $X=\lbrace A_1,A_2,\ldots,A_N\rbrace$. For $j=1,2,\ldots,M$, perform the following operation: > > * Insert $B_j$ into $X$. Then, remove one median of $X$ from $X$. > > Find the sum of elements in $X$ when all operations are finished. What is a median?When $N$ is even, the median of a multiset $X$ with $N+1$ elements is the $\left(1+\frac{N}{2}\right)$\-th value in ascending order among the elements of $X$. For example, the median of $X=\lbrace 1, 3, 4, 5, 8\rbrace$ is $4$, and the median of $X=\lbrace 2,2,2\rbrace$ is $2$. Note that in this problem, the multiset for which we consider the median always has an odd number of elements. ## Constraints * $1\leq N,M,Q\leq 2\times 10^5$ * $N$ is even. * $1\leq A_i\leq 10^9$ * $1\leq B_i\leq 10^9$ * $t_q\in\lbrace 1,2\rbrace$ * If $t_q=1$, then $1\leq i_q\leq N$ * If $t_q=2$, then $1\leq i_q\leq M$ * $1\leq x_q\leq 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $Q$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$ $t_1$ $i_1$ $x_1$ $\vdots$ $t_Q$ $i_Q$ $x_Q$ [samples]

Samples

Input #1

Output #1

10
13

First, the $1$\-st query makes $A=(5,1,3,3)$ and $B=(1,2)$. In this case, the operations in the subproblem proceed as follows.

*   Initialize $X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace$.
*   Insert $B_1=1$ into $X$, making $X=\lbrace 1,1,3,3,5\rbrace$. Then, remove one median from $X$, making $X=\lbrace 1,1,3,5\rbrace$.
*   Insert $B_2=2$ into $X$, making $X=\lbrace 1,1,2,3,5\rbrace$. Then, remove one median from $X$, making $X=\lbrace 1,1,3,5\rbrace$.

The sum of elements in $X$ when all operations are finished is $1+1+3+5=10$.
Next, the $2$\-nd query makes $A=(5,1,3,3)$ and $B=(5,2)$. In this case, the operations in the subproblem proceed as follows.

*   Initialize $X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace$.
*   Insert $B_1=5$ into $X$, making $X=\lbrace 1,3,3,5,5\rbrace$. Then, remove one median from $X$, making $X=\lbrace 1,3,5,5\rbrace$.
*   Insert $B_2=2$ into $X$, making $X=\lbrace 1,2,3,5,5\rbrace$. Then, remove one median from $X$, making $X=\lbrace 1,2,5,5\rbrace$.

The sum of elements in $X$ when all operations are finished is $1+2+5+5=13$.

Input #2

6 7 5
7 1 2 5 5 3
4 2 5 1 3 3 8
2 1 3
2 7 1
1 3 6
2 4 2
1 5 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Remove Median Operations",
    "description": {
      "content": "You are given an integer sequence $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ and an integer sequence $B=(B_1,B_2,\\ldots,B_M)$ of length $M$. Here, $N$ is **even**. You are given $Q$ queries. The $q$\\-th q",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc210_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ and an integer sequence $B=(B_1,B_2,\\ldots,B_M)$ of length $M$. Here, $N$ is **even**.\nYou are given $Q$ queries. The $q$\\-th q...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments