A7715. Chargers
编程题
普及/提高-
知识点
题目描述
有一个充电器，其充电插槽数量无限。在时刻 $0$，所有插槽均为空。
一块电池的最大容量为 $V$。当一块电池插入插槽后，它将以速率 $1$ 充电，直至其电量达到最大容量（即：每经过 $1$ 单位时间，电量增加 $1$）。
按顺序处理 $Q$ 个查询。第 $q$ 个查询以以下两种格式之一给出。此处保证 $t_1 < \dots < t_Q$。
* 类型 $1$（$1\ t_q\ w_q$）：在时刻 $t_q$，将一块当前电量为 $w_q$ 的电池插入一个插槽。
* 类型 $2$（$2\ t_q$）：在时刻 $t_q$，从插槽中拔出电量最高的那块电池，并输出其电量。若没有任何电池插入插槽，则输出 $-1$。
一块电池的最大容量为 $V$。当一块电池插入插槽后，它将以速率 $1$ 充电，直至其电量达到最大容量（即：每经过 $1$ 单位时间，电量增加 $1$）。
按顺序处理 $Q$ 个查询。第 $q$ 个查询以以下两种格式之一给出。此处保证 $t_1 < \dots < t_Q$。
* 类型 $1$（$1\ t_q\ w_q$）：在时刻 $t_q$，将一块当前电量为 $w_q$ 的电池插入一个插槽。
* 类型 $2$（$2\ t_q$）：在时刻 $t_q$，从插槽中拔出电量最高的那块电池，并输出其电量。若没有任何电池插入插槽，则输出 $-1$。
输入格式
输入从标准输入中按以下格式给出：
> $Q$ $V$
> $\mathrm{query}_1$
> $\vdots$
> $\mathrm{query}_Q$
其中，$\mathrm{query}_q$ 表示第 $q$ 个查询，其格式为以下两种之一：
> $1$ $t_q$ $w_q$
> $2$ $t_q$
> $Q$ $V$
> $\mathrm{query}_1$
> $\vdots$
> $\mathrm{query}_Q$
其中，$\mathrm{query}_q$ 表示第 $q$ 个查询，其格式为以下两种之一：
> $1$ $t_q$ $w_q$
> $2$ $t_q$
输出格式
设 $x$ 为类型 $2$ 的查询次数。输出 $x$ 行。
第 $k$ 行（$1 \leq k \leq x$）应包含第 $k$ 个类型 $2$ 查询所对应的输出值。
第 $k$ 行（$1 \leq k \leq x$）应包含第 $k$ 个类型 $2$ 查询所对应的输出值。
输入输出样例
输入 #1
7 100 1 15 60 1 25 80 2 30 1 45 0 2 60 2 70 2 80
输出 #1
85 100 25 -1
输入 #2
20 380736236 1 21873985 256702097 2 86369729 1 114301317 288304981 1 147244640 305840435 2 150951976 1 331581391 50335458 1 352989552 47577202 1 400130024 345362760 2 458793150 2 509082216 1 591375600 197371572 1 617022014 101276068 1 679649471 310249627 1 796351653 268586022 1 825648347 129608152 2 908069704 2 921770319 1 949684819 372272469 1 971850999 335461408 2 986253026
输出 #2
321197841 324955640 380736236 380736236 380736236 380736236 380736236
说明/提示
**样例 1 解释：**
七个查询按如下顺序处理。
* 在时刻 $15$，插入一块电量为 $60$ 的电池。此时充电器中有一块电量为 $60$ 的电池。
* 在时刻 $25$，插入一块电量为 $80$ 的电池。此时充电器中有两块电池，电量分别为 $70$ 和 $80$。
* 在时刻 $30$，充电器中的电池电量分别为 $75$ 和 $85$。其中，电量为 $85$ 的电池被拔出。
* 在时刻 $45$，插入一块电量为 $0$ 的电池。此时充电器中有两块电池，电量分别为 $0$ 和 $90$。
* 在时刻 $60$，充电器中的电池电量分别为 $15$ 和 $100$。其中，电量为 $100$ 的电池被拔出。
* 在时刻 $70$，充电器中仅有一块电量为 $25$ 的电池。该电量为 $25$ 的电池被拔出。
* 在时刻 $80$，没有电池插入充电器。因此，没有电池被拔出。
### 约束条件
* $1 \leq Q \leq 3 \times 10^5$
* $1 \leq V \leq 10^9$
* 对于类型 $1$ 的查询，满足 $1 \leq t_q \leq 10^9$。
* 对于类型 $1$ 的查询，满足 $0 \leq w_q \leq V$。
* 对于类型 $2$ 的查询，满足 $1 \leq t_q \leq 10^9$。
* $t_1 < \dots < t_Q$
* 所有输入值均为整数。
七个查询按如下顺序处理。
* 在时刻 $15$，插入一块电量为 $60$ 的电池。此时充电器中有一块电量为 $60$ 的电池。
* 在时刻 $25$，插入一块电量为 $80$ 的电池。此时充电器中有两块电池，电量分别为 $70$ 和 $80$。
* 在时刻 $30$，充电器中的电池电量分别为 $75$ 和 $85$。其中，电量为 $85$ 的电池被拔出。
* 在时刻 $45$，插入一块电量为 $0$ 的电池。此时充电器中有两块电池，电量分别为 $0$ 和 $90$。
* 在时刻 $60$，充电器中的电池电量分别为 $15$ 和 $100$。其中，电量为 $100$ 的电池被拔出。
* 在时刻 $70$，充电器中仅有一块电量为 $25$ 的电池。该电量为 $25$ 的电池被拔出。
* 在时刻 $80$，没有电池插入充电器。因此，没有电池被拔出。
### 约束条件
* $1 \leq Q \leq 3 \times 10^5$
* $1 \leq V \leq 10^9$
* 对于类型 $1$ 的查询，满足 $1 \leq t_q \leq 10^9$。
* 对于类型 $1$ 的查询，满足 $0 \leq w_q \leq V$。
* 对于类型 $2$ 的查询，满足 $1 \leq t_q \leq 10^9$。
* $t_1 < \dots < t_Q$
* 所有输入值均为整数。