← 返回题目列表

AtCoder · abc241_d

G. 顺序查询

中文机器翻译题面 查看原题

分数: 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.