問題一覧 > 通常問題

No.3298 K-th Slime

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 132
作問者 : Nafmo2 / テスター : dyktr_06 くらげ sepa38 おのせ
お気に入りにしたユーザー ProblemId : 12627 / 自分の提出
問題文最終更新日: 2025-10-09 12:26:33
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もしくは右上の雲マークをクリックしてアカウントを作成してください。