102413: [AtCoder]ABC241 D - Sequence Query
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
问题描述
我们有一个空序列$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$。