← 返回题目列表

Codeforces · 1028/D

D. 订单簿

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

让我们考虑一些股票的订单簿的简化版本。 The order book is a list of orders (offers) from people that want to buy or sell one unit of the stock, each order is described by direction (BUY or SELL) and price.

在任何时刻,每个卖出报价的价格都高于每个买入报价。

在这个问题中,任何两个曾经存在的订单都不会具有相同的价格。

最低价的卖单和最高价的买单称为最佳报价,如下图黑框所示。

所提供的订单簿显示有人想要以 $$$12$$$ 的价格出售该产品,这是最好的卖出报价,因为其他两个价格更高。最佳买入报价的价格为 $$$10$$$。

此订单簿中有两种可能的操作:

1. 有人以某个价格添加了某个方向的新订单。
2. 有人接受最好的卖出或买入报价(达成交易)。不可能接受不是最好的卖出或买入报价(以更差的价格进行交易)。当有人接受报价后,该报价就会从订单簿中永久删除。

只允许以低于最佳卖出报价的价格添加新的买入订单(如果您想以更高的价格购买股票,那么您应该接受最佳卖出报价,而不是添加订单)。同样,无法添加价格低于或等于最佳买入报价的新卖出订单。例如,如果已有报价“购买 $$$20$$$”或“购买 $$$25$$$”,则您无法添加新报价“出售 $$$20$$$”——在这种情况下,您只需接受最佳的购买报价。

您的订单簿日志已损坏(一开始订单簿中没有订单)。每个动作都有以下两种类型之一:

1.“ADD $$$p$$$”表示添加新订单,价格为$$$p$$$,方向未知。该订单不得与尚未从订单簿中删除的订单相矛盾。
2.“接受$$$p$$$”表示接受价格为$$$p$$$且方向未知的现有最佳报价。

所有操作的方向都丢失。日志中的信息并不总是足以确定这些方向。计算正确恢复所有 ADD 动作方向的方法数量,以便在任何时刻满足所有描述的条件。由于答案可能很大,因此输出它对 $$$10^9 + 7$$$ 取模。如果无法正确恢复方向,则输出$$$0$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 363\,304$$$) — 日志中的操作数。

接下来的 $$$n$$$ 行包含一个字符串“ACCEPT”或“ADD”和一个整数 $$$p$$$ ($$$1 \le p \le 308\,983\,066$$$),描述操作类型和价格。

所有 ADD 操作都有不同的价格。对于接受操作,保证相同价格的订单已被添加但尚未被接受。

输出

输出以 $$$10^9 + 7$$$ 为模恢复 ADD 动作方向的方法数量。

示例

输入 #1

6
ADD 1
ACCEPT 1
ADD 2
ACCEPT 2
ADD 3
ACCEPT 3

输出 #1

8

输入 #2

4
ADD 1
ADD 2
ADD 3
ACCEPT 2

输出 #2

2

输入 #3

7
ADD 1
ADD 2
ADD 3
ADD 4
ADD 5
ACCEPT 3
ACCEPT 5

输出 #3

0

注意

在第一个示例中,每个订单都可以是“买入”或“卖出”。

在第二个示例中,价格为 $$$1$$$ 的订单必须是买入订单,价格为 $$$3$$$ 的订单必须是卖出订单。