Задача 11 из 21

Приём винограда

Время 3 с · память 256 МБ

В период сбора урожая на винограднике работают KK приёмщиков винограда; им присвоены номера начиная с единицы. Каждый приёмщик принимает урожай только одного сорта: приёмщики с нечётными номерами — сорт A, с чётными — сорт B. Для каждой из NN партий урожая известны сорт и назначенные время начала и время окончания приёмки в минутах от начала рабочего дня.

Партии рассматривают в порядке возрастания времени начала приёмки. Очередную партию направляют к свободному приёмщику нужного сорта с минимальным номером. Приёмщик начинает приёмку следующей партии не ранее чем через 5 минут после окончания приёмки предыдущей. Если свободных приёмщиков нужного сорта нет, партию передают на рынок для продажи.

Если время начала у нескольких партий совпадает, раньше рассматривают партию с меньшим временем окончания, а при совпадении и его — партию сорта A.

Определите количество партий, принятых приёмщиками, и номер приёмщика, принявшего ту партию, которая была принята последней в указанном порядке рассмотрения.

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

В первой строке находятся два натуральных числа, не превышающих 10 00010\,000: KK — количество приёмщиков и NN — количество партий. Каждая из следующих NN строк содержит два целых числа — время начала и время окончания приёмки партии (от 0 до 1440, время начала не больше времени окончания) — и заглавную латинскую букву A или B, обозначающую сорт.

Партии идут в произвольном порядке и могут повторяться. Гарантируется, что хотя бы одна партия будет принята.

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

Выведите два целых числа: сначала количество принятых партий, затем номер приёмщика, принявшего ту партию, которая была принята последней.

Примеры

Ввод 1
2 6
30 60 A
65 1000 A
65 1000 B
1010 1300 B
65 900 A
905 1100 A
Вывод 1
5 2
Ввод 2
1 4
0 10 A
15 20 A
14 15 A
25 25 B
Вывод 2
2 1

Примечание

В первом примере приёмщик 1 принимает партии (30, 60, A), (65, 900, A) и (905, 1100, A), приёмщик 2 — партии (65, 1000, B) и (1010, 1300, B); партия (65, 1000, A) передана на рынок. Последней принята партия (1010, 1300, B), ответ — 5 и 2. Во втором примере партию с началом приёмки в момент 14 принять нельзя: приёмщик освободится только в момент 15. Для сорта B приёмщика нет.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче