#STL008. 紧急任务池

紧急任务池

紧急任务池

任务池最初为空。每个任务有编号 id 和紧急程度 priority。新任务可以随时加入;取任务时,总是先取最紧急的一个。如果几个任务一样紧急,先取编号最小的那个。

支持以下指令:

  • ADD id priority:加入任务,不输出。
  • TAKE:取出并删除优先级最高的任务,输出它的 id;池为空时输出 EMPTY。

一个 id 在整个输入中最多用于一次 ADD,即使对应任务已经被取走,也不能再次使用这个 id。不同任务允许具有相同的 priority。

输入格式

第一行整数 q。接下来 q 行,每行一条上述指令。

输出格式

按 TAKE 出现的顺序,每次输出一行。若没有 TAKE,输出为空。

数据范围

  • 1 ≤ q ≤ 200000。
  • 每次 ADD 满足 1 ≤ id ≤ q,且所有 ADD 的 id 互不相同。
  • 0 ≤ priority ≤ 10⁹。
  • 输入保证指令格式合法。

样例 1

输入:

10
TAKE
ADD 5 7
ADD 2 7
ADD 9 3
TAKE
ADD 1 8
TAKE
TAKE
TAKE
TAKE

输出:

EMPTY
2
1
5
9
EMPTY

解释:第一次取任务时任务池为空。编号 5 和 2 的紧急程度都是 7,所以先取 2;随后新加入的编号 1 的紧急程度为 8,先于编号 5 和 9 被取走。最后池为空。

样例 2

输入:

8
ADD 8 0
ADD 3 0
ADD 6 1000000000
TAKE
TAKE
ADD 1 0
TAKE
TAKE

输出:

6
3
1
8

解释:编号 6 的紧急程度最高,先被取走。剩余任务的紧急程度均为 0,依次按当前池中的编号从小到大取出:先 3,加入 1 后先 1,最后 8。