← 返回题目列表

AtCoder · tenka1_2013_qualB_b

B. Tenkaichi后进先出数据结构

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

問題文

栈是最基本的数据结构之一,用于以后进先出(LIFO)的结构保存数据。栈最初是空的,可以添加和取出元素,但取出是按添加的顺序的逆序进行的。

有一天,在天下一株式会社工作的优也君,被下达了一个任务——扮演成su塔kk。对此目瞪口呆的优也君,你出于关心,决定代他处理以如下格式输入的指令序列,并制作一个程序生成后述的输出。


入力

输入是按以下格式从标准输入给出的。

Q L
query_1
query_2
...
query_Q
  • 1 每行是给定的指令数量 Q (1 \leq Q \leq 10^5)以及栈的大小 L (1 \leq L \leq 2147483647) 用空格分隔。 在
  • 2 从行 Q+1 到第…行 Q 行是、i (1 \leq i \leq Q第)个指令被给出。

每条指令属于以下 4 种类型之一。

  1. 推 N M
    • 向栈中添加元素 M 该值应乘以 N 个。不会输出。
  2. 流行音乐 N
    • 从栈中取出元素 N 个。不会输出。
  3. 顶部
    • 将栈顶元素 1 行输出。这个指令不会改变构成su塔kk的元素。
  4. 尺寸
    • 输出栈的元素数量 1 行数。

N, M 都是整数, 1 \leq N \leq 10^5, -2^{20} \leq M \leq 2^{20} 已满足。

但是,栈的顶部元素是指在栈中最后添加的元素,如果当时进行了 1操作,则会被取出的元素。

部分点

  • Q \leq 50, N \leq 50 正确输入60 作为满分的部分分数,30 点。 如果您正确回答了所有满足

出力

如上所述,它按顺序处理给定的命令,并在给出 Top 或 Size 输入时输出。

但是,以下内容 3 在两种情况下,堆栈将抛出异常并停止。

  • 推 N M 与元素数量 L-N 当完成更大的堆栈时 当堆栈小于
  • 流行音乐 N与元素数量 N 时
  • 在空堆栈上执行 Top 时

堆栈抛出的异常如下。

  • 如果程序因Push引起的异常而终止, FULL
  • 如果程序由于 Pop 或 Top 引起的异常而终止, EMPTY

这些例外是 它在 1 行上输出,并且堆栈在抛出异常后丢弃进一步的指令。
如果堆栈能够成功处理指令直到结束, 输出 SAFE 该值应乘以 1 行并退出。


入力例 1

7 20
Push 2 3
Push 4 5
Top
Size
Pop 5
Top
Size

出力例 1

5
6
3
1
SAFE

入力例 2

1 10
Push 40 40

出力例 2

FULL

入力例 3

5 10
Push 1 2
Top
Pop 1
Top
Size

出力例 3

2
EMPTY

入力例 4

4 10
Top
Size
Push 1 1
Top

出力例 4

EMPTY