Олимпиадный тренинг

Задача . B. Биржевые заявки


Задача

Темы: жадные алгоритмы реализация сортировки Структуры данных *1300

В данной задаче вам потребуется обработать набор заявок на торгах и сформировать по ним биржевой стакан.

Заявка — это желание какого-то участника торгов купить или продать акции. Для каждой заявки i известна ее цена pi, направление заявки di — покупка или продажа, а также количество акций qi, которые участник готов купить или продать по цене pi за акцию. Значение 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' — продажу. Цена любой заявки на продажу больше цены любой заявки на покупку.

Выходные данные

Выведите не больше чем 2s строк, в которых содержатся аггрегированные заявки биржевого стакана глубины s. Заявки требуется выводить в том же формате что и во входных данных.

Примечание

Будем обозначать (x, y) заявку по цене x с объемом y. В тестовом примере имеются три аггрегированные заявки на покупку: (10, 3), (20, 4), (25, 10) и две на продажу: (50, 8), (40, 1)

Нужно вывести не более двух лучших заявок по каждому направлению, поэтому заявку (10 3), имеющую худшую цену среди заявок на покупку, выводить не нужно.


Примеры
№Входные данныеВыходные данные
1 6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10 
S 50 8
S 40 1
B 25 10
B 20 4

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет