分数: 400 点
问题陈述
我们有一个空序列 A.
鉴于 Q 查询,按顺序处理。
每个查询属于以下三种类型之一。
-
1 x:插入 x to A. -
2 x k:其中的元素 A 小于或等于 x,打印 k- 第一个最大值。 (k 不超过 \bf{5})
如果少于 k 的元素 A 小于或等于 x,然后打印-1. -
3 x k:其中的元素 A 大于或等于 x,打印 k- 第一个最小值。 (k 不超过 \bf{5})
如果少于 k 的元素 A 大于或等于 x,然后打印-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)。
另外给出了
If c_i=1,那么 x ;如果
另外给出了 c_i=2, 3,那么 x 和 k 。
换句话说,每个查询都以以下三种格式之一给出:
1 x
2 x k
3 x k
输出
打印 q 行,其中 q 是查询数量,使得 c_i=2,3.
的 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-nd 是 20;的 3-rd 是 30.