← 返回题目列表

Codeforces · 916/D

D. 杰米和待办事项列表

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

为什么我要完成这么多作业???

杰米的学校生活变得非常忙碌。他开始忘记他必须做的任务。他决定把这些事情写在待办事项清单上。他为每项任务分配一个值优先级(值越低意味着越重要),以便他可以决定需要花更多时间在哪个任务上。

几天后,Jamie 发现该列表太大了,他甚至无法自己管理该列表!由于您是 Jamie 的好朋友,请帮助他编写一个程序来支持待办事项列表上的以下操作:

- 设置 ai xi — 如果作业 ai 不存在,则将其添加到待办事项列表中,并将其优先级设置为 xi。如果任务 ai 已在待办事项列表中,则其优先级将更改为 xi。
- 删除 ai — 从待办事项列表中删除作业 ai(如果存在)。
- 查询 ai — 输出比作业 ai 更重要(具有较小优先级值)的作业数量,以便 Jamie 可以决定更好的时间表。如果 ai 不在待办事项列表中,则输出  - 1。
- undo di — 撤消之前 di 天内(不包括本次操作当天)所做的所有更改

在第 0 天,待办事项列表为空。在接下来的 q 天内,Jamie 将执行四项操作中的一项。如果操作是查询,则应该在继续第二天之前输出查询的结果,否则可怜的 Jamie 无法做出适当的决定。

输入

第一行由一个整数 q (1 ≤ q ≤ 105) 组成 - 操作数。

以下 q 行包含操作的描述。第 i 行包含 Jamie 在第 i 天完成的操作。查询具有以下格式:

行中的第一个字指示操作类型。它必须是以下四种之一:设置、删除、查询、撤消。

- 如果是集合运算,则后面是字符串 ai 和整数 xi (1 ≤ xi ≤ 109)。 ai 是需要设置为优先级 xi 的分配。
- 如果是删除操作,则后面跟着字符串 ai。 ai 是需要删除的作业。
- 如果是查询操作,则后面跟着字符串ai。 ai是需要查询的作业。
- 如果是撤消操作,则后面跟着一个整数di (0 ≤ di < i)。 di 是需要撤消更改的天数。

所有赋值名称 ai 仅由小写英文字母组成,长度为 1 ≤ |ai| ≤ 15。

保证最后一个操作是查询操作。

互动

如果操作是查询,则应输出查询结果并刷新输出流,然后再继续下一个操作。否则,您可能会得到 Idleness Limit Exceed 的判决。

要刷新输出流,请参阅您选择的编程语言的文档。下面列出了一些常见编程语言的flush函数:

- C: fflush(stdout);
- C++: cout « 刷新;
- Java: System.out.flush();

输出

对于每个查询操作,输出一个整数 - 优先级低于分配 ai 的分配数量,或者 - 如果 ai 不在待办事项列表中,则为 1。

示例

输入 #1

8
set chemlabreport 1
set physicsexercise 2
set chinesemockexam 3
query physicsexercise
query chinesemockexam
remove physicsexercise
query physicsexercise
query chinesemockexam

输出 #1

1
2
-1
1

输入 #2

8
set physicsexercise 2
set chinesemockexam 3
set physicsexercise 1
query physicsexercise
query chinesemockexam
undo 4
query physicsexercise
query chinesemockexam

输出 #2

0
1
0
-1

输入 #3

5
query economicsessay
remove economicsessay
query economicsessay
undo 2
query economicsessay

输出 #3

-1
-1
-1

输入#4

5
set economicsessay 1
remove economicsessay
undo 1
undo 1
query economicsessay

输出#4

-1