← 返回题目列表

Codeforces · 1089/K

K. King Kog 的招待会

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

科格国王对他的骑士们一贯的松懈感到恼火——他们可以在没有事先通知的情况下闯入他的大厅!因此,国王决定建立一个带有队列的接待处,每个骑士提前选择他来的时间和访问需要多长时间。骑士们按照记录的时间顺序接受服务,但每个骑士必须等到他之前的所有骑士都访问完毕。

Keabeanie 公主想见她的父亲。然而,她不想打扰骑士们,所以她加入了队列。不幸的是,骑士们经常改变主意——他们可以加入队列或取消访问。根据接待处的记录,请帮助公主了解如果她在指定时间排队,她需要等待多长时间才能见到父亲。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$) — 事件数。事件可以分为三种类型: 加入, 取消,或 查询.

  • 加入“+ $$$t$$$ $$$d$$$" ($$$1 \leq t, d \leq 10^6$$$) — 一个新骑士加入队列,其中 $$$t$$$ 是骑士到来的时间,$$$d$$$ 是访问的持续时间。
  • 取消“- $$$i$$$" ($$$1 \leq i \leq q$$$) — 骑士取消访问,其中 $$$i$$$ 是所有事件列表中相应加入事件的编号(从 1 开始计数)。
  • 查询“? $$$t$$$" ($$$1 \leq t \leq 10^6$$$) — Keabeanie 询问如果她在 $$$t$$$ 时间到达,她会等多久。

保证每次活动结束后队列中不存在两个进入时间相同的骑士。取消事件是指之前尚未取消的连接。

Keabeanie可以和一些骑士同时到来,但是Keabeanie非常有礼貌,她会等待骑士通过。

输出

对于每个查询,单独一行写出 Keabeanie 必须等待的时间。

示例

输入
复制

19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6

输出
复制

0
1
0
2
1
3
2
1
2
1
0
0
2
1
1