#P11861. [CCC 2025 Senior] 写作业 / To-Do List
[CCC 2025 Senior] 写作业 / To-Do List
题目背景
译自 CCC 2025 Senior T5。本题满分为 。
题目描述
你的待办事项列表现在是空的。但是你需要处理 次对待办事项列表的更新:
-
:
向你的待办事项列表内加入一个任务:这个任务在第 秒发布,需要 秒完成。
-
:
删除第 个被加入的任务。
在每次操作后,求出最早能在什么时候完成列表中所有的任务。
一次只能完成一个任务。一旦开始一个任务,必须一口气完成,不能中途去做别的任务。
为了锻炼你的水平,我们会使用一些手段让你在线处理更新。
输入格式
第一行,一个正整数 。
接下来 行,每行一个大写字母 和若干个非负整数,描述一次加密的操作:
令 , 表示上一次更新后的答案(如果不存在,定义为 )。则 ,,。
你的待办事项列表现在是空的。但是你需要处理 次对待办事项列表的更新:
-
:
向你的待办事项列表内加入一个任务:这个任务在第 秒发布,需要 秒完成。
-
:
删除第 个被加入的任务。
在每次操作后,求出最早能在什么时候完成列表中所有的任务。
一次只能完成一个任务。一旦开始一个任务,必须一口气完成,不能中途去做别的任务。
为了锻炼你的水平,我们会使用一些手段让你在线处理更新。
数据保证不会删除不存在(或已被删除)的任务,且保证在每次更新后,列表中至少有一个任务。
输出格式
输出 行,每行一个正整数,表示答案。
6
A 3 3
A 2 0
A 999996 999995
D 999991
A 1000000 999994
D 999992
5
11
13
11
13
9
2
A 1000000 1000000
A 4 4
1999999
2999999
提示
样例解释
- 样例 解释:
加密前的样例 为
6
A 3 3
A 7 5
A 4 3
D 1
A 8 2
D 2
-
在第一次更新后,我们可以在第二秒的开始时开始第一次任务,并在第五秒的结束时完成(区间 )。
-
在第二次更新后,我们可以在区间 上完成第一次任务,在区间 上完成第二次任务。
-
在第三次更新后,我们可以在区间 上完成第一次任务,在区间 上完成第三次任务,然后在区间 上完成第二次任务。
-
在第四次更新后,我们可以在区间 上完成第三次任务,在区间 上完成第二次任务。
-
在第五次更新后,我们可以在区间 上完成第三次任务,在区间 上完成第二次任务,然后在区间 上完成第四次任务。
-
在第六次更新后,我们可以在区间 上完成第三次任务,在区间 上完成第四次任务。
-
样例 解释:
加密前的样例 为
2
A 1000000 1000000
A 1000000 1000000
子任务
对于 的数据,保证:
- ;
- ;
- 不会删除不存在(或已被删除)的任务。
- 在每次更新后,列表中至少有一个任务。
- :样例。
- :。
- :只有第一种更新。
- :无额外限制。