問題一覧 > 通常問題

No.649 Time for a Little QK Here!

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 286
作問者 : kakira9618 / テスター : matsu7874
お気に入りにしたユーザー ProblemId : 2120 / 自分の提出
問題文最終更新日: 2018-10-13 04:32:01
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 183 (順位表) の他の問題:

Problem Statement

You are given integers $Q$ and $K$.
Process the following queries ($Q$ in total).

  • Type 1: Add the number $v$ to the array $S$.
  • Type 2: If the number of elements in the array $S$ is at least $K$, print the $K$-th smallest element of $S$ and remove one such element from $S$. If the number of elements in $S$ is less than $K$, print -1.

(Note: $K$ is the same for all type 2 queries.)

Input

$Q$ $K$
$query_1$
$query_2$
…
$query_Q$

All input values are integers.

$Q (1\leq Q\leq200000)$ represents the number of queries.
$K (1\leq K\leq200000)$ indicates which smallest number must be answered in type 2 queries.

The following $Q$ lines give the information of the queries.
$query_i$ represents the $i$-th query. Each query is given in the following format.

For a type 1 query: 
$1\ v_i$
For a type 2 query: 
$2$

Here, $v_i (0\leq v_i\leq10^{18})$ represents the number to add to the array in the $i$-th query (type 1).
There is at least one type 2 query.

The input and output have many lines, so be careful with IO! Especially for LL languages, take care because the constraints are tight!

Output

Print the results of the type 2 queries, separated by newlines. Print a newline at the end.

Sample

Sample 1
Input
15 3
1 3
1 4
1 5
2
2
1 10
1 10
1 1
2
1 3
2
1 1000
2
1 0
2
Output
5
-1
4
3
10
3

The array $S$ changes as follows.

  • Queries 1 to 3: $S = \{3, 4, 5\}$
  • Query 4: print 5, $S = \{3, 4\}$
  • Query 5: print -1, $S = \{3, 4\}$
  • Queries 6 to 8: $S = \{1, 3, 4, 10, 10\}$
  • Query 9: print 4, $S = \{1, 3, 10, 10\}$
  • Query 10: $S = \{1, 3, 3, 10, 10\}$
  • Query 11: print 3, $S = \{1, 3, 10, 10\}$
  • Query 12: $S = \{1, 3, 10, 10, 1000\}$
  • Query 13: print 10, $S = \{1, 3, 10, 1000\}$
  • Query 14: $S = \{0, 1, 3, 10, 1000\}$
  • Query 15: print 3, $S = \{0, 1, 10, 1000\}$
Sample 2
Input
4 1
1 10
1 10
2
2
Output
10
10

Queries may cause the array $S$ to contain duplicate elements.
Note that even when there are duplicates, a type 2 query removes only one element.

Sample 3
Input
4 2
1 9
1 10000000000000000
1 90000000000000000
2
Output
10000000000000000

Large numbers may be given as input. The numbers are 9, 10 quadrillion, and 90 quadrillion, so print 10 quadrillion, the second smallest.

Sample 4
Input
1 1
2
Output
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。