102413: [AtCoder]ABC241 D - Sequence Query

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

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$.

Input

题意翻译

# 题意简述 有一个空序列 $A$。给定 $Q$ 次操作,每次询问是以下三种之一: >`1 x`:向 $A$ 中插入元素 $x$。 > >`2 x k`:输出 $A$ 中所有 $\le x$ 的元素中的第 $k$ 大值。如果不存在输出 `-1`。 > >`3 x k`:输出 $A$ 中所有 $\ge x$ 的元素中的第 $k$ 小值。如果不存在输出 `-1`。 # 数据范围 >$1\le Q\le2\times10^5$。 > >$1\le x\le10^{18}$。 > >$1\le k\le5$。 > >所有输入均为整数。 # 输入格式 第一行包含一个整数 $Q$,接下来 $Q$ 行每行一次操作。 具体询问输入参考题意简述。 # 输出格式 对于操作 $2,3$,输出一个数表示答案。 Translated by @[tianbiandeshenghuo1](/user/714285)

Output

得分:400分

问题描述

我们有一个空序列$A$。

给定$Q$个查询,按顺序处理它们。

每个查询是以下三种类型之一:

  • 1 x:将$x$插入到$A$中。

  • 2 x k:在$A$中小于或等于$x$的元素中,打印第$k$个最大的值。($k$不超过$\bf{5}$)
    如果小于或等于$x$的$A$元素少于$k$个,则打印-1

  • 3 x k:在$A$中大于或等于$x$的元素中,打印第$k$个最小的值。($k$不超过$\bf{5}$)
    如果大于或等于$x$的$A$元素少于$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$。

换句话说,每个查询采用以下三种格式之一:

$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个是$20$;第3个是$30$。

加入题单

上一题 下一题 算法标签: