#P11861. [CCC 2025 Senior] 写作业 / To-Do List

[CCC 2025 Senior] 写作业 / To-Do List

题目背景

译自 CCC 2025 Senior T5。本题满分为 1515

题目描述

你的待办事项列表现在是空的。但是你需要处理 qq 次对待办事项列表的更新:

  • A\texttt{A} ss tt

    向你的待办事项列表内加入一个任务:这个任务在第 ss 秒发布,需要 tt 秒完成。

  • D\texttt{D} xx

    删除第 xx 个被加入的任务。

在每次操作后,求出最早能在什么时候完成列表中所有的任务。

一次只能完成一个任务。一旦开始一个任务,必须一口气完成,不能中途去做别的任务。

为了锻炼你的水平,我们会使用一些手段让你在线处理更新。

输入格式

第一行,一个正整数 qq

接下来 qq 行,每行一个大写字母 cA,Dc\in \texttt{A},\texttt{D} 和若干个非负整数,描述一次加密的操作:

  • A\texttt{A} ss' tt'
  • D\texttt{D} xx'

p=106+3p=10^6+3last\mathrm{last} 表示上一次更新后的答案(如果不存在,定义为 00)。则 s=(s+last)modps=(s'+\mathrm{last})\bmod pt=(t+last)modpt=(t'+\mathrm{last})\bmod px=(x+last)modpx=(x'+\mathrm{last})\bmod p

你的待办事项列表现在是空的。但是你需要处理 qq 次对待办事项列表的更新:

  • A\texttt{A} ss tt

    向你的待办事项列表内加入一个任务:这个任务在第 ss 秒发布,需要 tt 秒完成。

  • D\texttt{D} xx

    删除第 xx 个被加入的任务。

在每次操作后,求出最早能在什么时候完成列表中所有的任务。

一次只能完成一个任务。一旦开始一个任务,必须一口气完成,不能中途去做别的任务。

为了锻炼你的水平,我们会使用一些手段让你在线处理更新。

数据保证不会删除不存在(或已被删除)的任务,且保证在每次更新后,列表中至少有一个任务。

输出格式

输出 qq 行,每行一个正整数,表示答案。

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

提示

样例解释

  • 样例 11 解释:

加密前的样例 11

6
A 3 3
A 7 5
A 4 3
D 1
A 8 2
D 2
  • 在第一次更新后,我们可以在第二秒的开始时开始第一次任务,并在第五秒的结束时完成(区间 [3,5][3, 5])。

  • 在第二次更新后,我们可以在区间 [3,5][3, 5] 上完成第一次任务,在区间 [7,11][7, 11] 上完成第二次任务。

  • 在第三次更新后,我们可以在区间 [3,5][3, 5] 上完成第一次任务,在区间 [6,8][6, 8] 上完成第三次任务,然后在区间 [9,13][9, 13] 上完成第二次任务。

  • 在第四次更新后,我们可以在区间 [4,6][4, 6] 上完成第三次任务,在区间 [7,11][7, 11] 上完成第二次任务。

  • 在第五次更新后,我们可以在区间 [4,6][4, 6] 上完成第三次任务,在区间 [7,11][7, 11] 上完成第二次任务,然后在区间 [12,13][12, 13] 上完成第四次任务。

  • 在第六次更新后,我们可以在区间 [4,6][4, 6] 上完成第三次任务,在区间 [8,9][8, 9] 上完成第四次任务。

  • 样例 22 解释:

加密前的样例 22

2
A 1000000 1000000
A 1000000 1000000

子任务

对于 100%100\% 的数据,保证:

  • 1q1061\le q\le 10^6
  • 1s,t1061\le s,t\le 10^6
  • 不会删除不存在(或已被删除)的任务。
  • 在每次更新后,列表中至少有一个任务。

  • Subtask 0(0 points)\text{Subtask 0(0 points)}:样例。
  • Subtask 1(2 points)\text{Subtask 1(2 points)}q3000q\le 3000
  • Subtask 2(6 points)\text{Subtask 2(6 points)}:只有第一种更新。
  • Subtask 3(7 points)\text{Subtask 3(7 points)}:无额外限制。