← 返回题目列表

Codeforces · 572/B

B. 订单簿

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

在此任务中,您需要处理一组证券交易所订单并使用它们来创建订单簿。

订单是某些参与者在证券交易所买卖股票的指令。订单号 i 具有价格 pi、方向 di(买入或卖出)和整数 qi。这意味着参与者准备以价格 pi 买入或卖出一只股票的 qi 股票。值 qi 也称为订单量。

具有相同价格 p 和方向 d 的所有订单将合并为一个具有价格 p 和方向 d 的聚合订单。该订单的数量是初始订单数量的总和。

订单簿是聚合订单的列表,其中第一部分包含按价格降序排序的卖单,第二部分包含也按价格降序排序的买单。

深度为 s 的订单簿包含每个方向的 s 个最佳聚合订单。如果价格较高,则买入订单更好;如果价格较低,则卖出订单更好。如果某个方向的聚合订单少于 s,则所有订单都将出现在最终订单簿中。

您收到 n 个股票交易指令。您的任务是打印这些订单的深度为 s 的订单簿。

输入

输入以两个正整数 n 和 s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50)、订单数和图书深度开始。

接下来的 n 行包含一个字母 di(“B”或“S”)、一个整数 pi (0 ≤ pi ≤ 105) 和一个整数 qi (1 ≤ qi ≤ 104) — 分别表示方向、价格和交易量。字母“B”表示买入,“S”表示卖出。任何卖单的价格均高于任何买单的价格。

输出

从深度为 s 的订单簿中打印不超过 2s 行的聚合订单。订单的输出格式应与输入格式相同。

示例

输入 #1

6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

输出 #1

S 50 8
S 40 1
B 25 10
B 20 4

注意

表示 (x, y) 具有价格 x 和数量 y 的订单。样本中有 3 个聚合买单 (10, 3)、(20, 4)、(25, 10) 和两个卖单 (50, 8)、(40, 1)。

您需要为每个方向打印不超过两个最佳订单,因此您不应打印买单中价格最差的订单 (10 3)。