/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
空の数列 A があります。
クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。
-
1 x： A に x を追加する。 -
2 x k： A の x 以下の要素のうち、大きい方から k 番目の値を出力する。(k は \bf{5} 以下)
ただし、A に x 以下の要素が k 個以上存在しないときは-1と出力する。 -
3 x k： A の x 以上の要素のうち、小さい方から k 番目の値を出力する。(k は \bf{5} 以下)
ただし、A に x 以上の要素が k 個以上存在しないときは-1と出力する。
制約
- 1\leq Q \leq 2\times 10^5
- 1\leq x\leq 10^{18}
- 1\leq k\leq 5
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
i 番目のクエリ \text{query}_i では、まずクエリの種類 c_i (1,2,3 のいずれか) が与えられる。
c_i=1 の場合は x が追加で与えられ、c_i=2,3 の場合は x,k が追加で与えられる。
すなわち、各クエリは以下に示す 3 つの形式のいずれかである。
1 x
2 x k
3 x k
出力
c_i=2,3 を満たすクエリの個数を q として q 行出力せよ。
j(1\leq j\leq q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。
入力例 1
11 1 20 1 10 1 30 1 20 3 15 1 3 15 2 3 15 3 3 15 4 2 100 5 1 1 2 100 5
出力例 1
20 20 30 -1 -1 1
\text{query}_{1,2,3,4} が終了した段階で、A=(20,10,30,20) となっています。
\text{query}_{5,6,7} について、A の 15 以上の要素は (20,30,20) です。
このうち小さい方から 1 番目の値は 20 、2 番目の値は 20 、3 番目の値は 30 です。
Score : 400 points
Problem Statement
We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.
-
1 x: Insert x to A. -
2 x k: Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
If there are less than k elements of A that are less than or equal to x, then print-1. -
3 x k: Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
If there are less than k elements of A that are greater than or equal to x, then print-1.
Constraints
- 1\leq Q \leq 2\times 10^5
- 1\leq x\leq 10^{18}
- 1\leq k\leq 5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
In the i-th query \text{query}_i, the type of query c_i (which is either 1, 2, or 3) is given first.
If c_i=1, then x is additionally given; if c_i=2, 3, then x and k are additionally given.
In other words, each query is given in one of the following three formats:
1 x
2 x k
3 x k
Output
Print q lines, where q is the number of queries such that c_i=2,3.
The j-th line (1\leq j\leq q) should contain the answer for the j-th such query.
Sample Input 1
11 1 20 1 10 1 30 1 20 3 15 1 3 15 2 3 15 3 3 15 4 2 100 5 1 1 2 100 5
Sample Output 1
20 20 30 -1 -1 1
After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).
For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.