No.3298 K-th Slime
問題文最終更新日: 2025-10-09 12:26:33
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest MMA Contest 020
(順位表)
の他の問題:
Problem Statement
There is a box containing $N$ slimes. The sizes of the slimes are $A_1, A_2, \ldots, A_N$.
You are given $Q$ queries; process them in order. There are $3$ types of queries, each given in one of the following formats.
1 x: Create a new slime of size $x$ and put it in the box.2 y: Take out $1$ slime that is the $K$-th smallest in the box. Increase its size by $y$ and put it back in the box.3: Print the size of the $K$-th smallest slime in the box.
Constraints
- $1 \leq K \leq N \leq 100{,}000$
- $1 \leq Q \leq 100{,}000$
- $1 \leq A_i \leq 10^{9} \ (1 \leq i \leq N)$
- $1 \leq x, y \leq 10^{9}$
- All input values are integers.
Input
$N \ K \ Q$ $A_1 \ A_2 \ \ldots \ A_N$ $query_1$ $\vdots$ $query_Q$
The $i$-th query $query_i$ is given in one of the following $3$ formats.
1 x
2 y
3
Output
If there are $X$ queries of the $3$rd type, print $X$ lines. On the $i$-th line $(1 \leq i \leq X)$, print the answer to the $i$-th query of the $3$rd type.
Sample
Sample 1
Input
5 3 8 1 2 3 4 5 1 6 3 2 4 3 1 10 3 2 10 3
Output
3 4 4 5
Initially, the box contains the slimes $[1,\ 2, \ 3, \ 4, \ 5]$. (Hereafter, the contents of a box containing $n$ slimes are denoted by $[a_1, \ldots, a_n]$.)
- Query $1$ : Create a slime of size $6$.
- Box: $[1,\ 2, \ 3, \ 4, \ 5, \ 6]$
- Query $2$ : Print the size of the $3$-rd smallest slime.
- Output: $3$
- Query $3$ : Take out the $3$-rd smallest slime, increase its size by $4$, and put it back.
- Box: $[1,\ 2, \ 4, \ 5, \ 6, \ 7]$
- Query $4$ : Print the size of the $3$-rd smallest slime.
- Output: $4$
- Query $5$ : Create a slime of size $10$.
- Box: $[1,\ 2, \ 4, \ 5, \ 6, \ 7, \ 10]$
- Query $6$ : Print the size of the $3$-rd smallest slime.
- Output: $4$
- Query $7$ : Take out the $3$-rd smallest slime, increase its size by $10$, and put it back.
- Box: $[1,\ 2, \ 5, \ 6, \ 7, \ 10, \ 14]$
- Query $8$ : Print the size of the $3$-rd smallest slime.
- Output: $5$
Sample 2
Input
5 3 13 3 8 5 2 9 2 6 2 1 1 1 1 10 2 7 1 4 3 1 10 1 8 3 1 5 2 3 3
Output
4 4 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
くらげ
sepa38