#STL001. 动态清单

动态清单

动态清单

清单管理员把编号逐个记在一张可伸长的清单末尾。请按照操作记录维护这张清单,并回答查询。清单初始为空;同一个编号可以出现多次。

输入格式

第一行是操作数 q。随后 q 条操作,每条为 PUSH x、POP、GET i 或 SIZE。

操作与输出格式

PUSH x 把 x 加到末尾,不输出。POP 删除并输出末尾值;清单为空则输出 EMPTY。GET i 输出第 i 项,采用 0 基下标;i 为负或 i 大于等于大小时输出 OUT_OF_RANGE。SIZE 输出当前大小。每个需要输出的操作占一行。

数据范围

1 ≤ q ≤ 200000;−10⁹ ≤ x ≤ 10⁹;−200000 ≤ i ≤ 200000。

时间限制:2000 ms;内存限制:256 MiB。输出按空白分隔的词比较。

样例 1

输入:

10
SIZE
POP
PUSH 7
PUSH -3
GET 0
GET 1
GET -1
POP
SIZE
GET 1

输出:

0
EMPTY
7
-3
OUT_OF_RANGE
-3
1
OUT_OF_RANGE

解释:SIZE 查询初始大小 0;弹空清单得到 EMPTY。加入 7、−3 后,下标 0 和 1 分别是 7、−3;负下标非法。弹出 −3 后剩一项,下标 1 越界。

样例 2

输入:

8
PUSH 1
PUSH 1
POP
GET 0
POP
POP
GET 200000
SIZE

输出:

1
1
1
EMPTY
OUT_OF_RANGE
0

解释:两个 1 分别保存。连续删除后清单为空,空删除和越界查询分别按规定输出。

创作记录

题面、样例、实现与数据由本题制作组依照公开的 C++ 标准库概念独立撰写,未使用第三方题面、故事、测试文件或程序。