Задача 12 из 21

Очереди в мастерской

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

В мастерской работают два окна приёма с номерами 1 и 2. Для каждого из NN посетителей известны время прихода, длительность обслуживания и вид услуги: услугу вида 1 оказывает только окно 1, услугу вида 2 — только окно 2, услугу вида 0 — любое окно.

Посетитель с услугой вида 0 выбирает окно, в очереди к которому меньше людей; если людей поровну, он выбирает окно 1. В очереди учитывается и тот посетитель, которого окно обслуживает в данный момент. Если в очереди к окну, в которое направляется посетитель, уже четыре человека, он уходит из мастерской без обслуживания; в другую очередь он не встаёт.

Каждое окно обслуживает посетителей по одному в порядке очереди и без перерывов; свободное окно начинает обслуживание сразу. Посетитель, обслуживание которого закончилось в момент прихода нового посетителя, в очереди уже не учитывается. Посетители, пришедшие одновременно, встают в очередь в том порядке, в каком они записаны во входных данных. Все посетители, вставшие в очередь, будут обслужены.

Определите количество посетителей, которых обслужит окно 2, и количество посетителей, которые уйдут без обслуживания.

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

В первой строке находится число NN — количество посетителей (натуральное число, не превышающее 100 000100\,000). Каждая из следующих NN строк содержит три целых числа: время прихода (от 0 до 10610^6), длительность обслуживания (от 1 до 10 00010\,000) и вид услуги (0, 1 или 2).

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

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

Выведите два целых числа: сначала количество посетителей, которых обслужит окно 2, затем количество посетителей, которые уйдут без обслуживания.

Примеры

Ввод 1
5
0 3 0
0 2 0
1 1 2
2 1 0
3 1 0
Вывод 1
3 0
Ввод 2
10
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
0 10 1
Вывод 2
0 6

Примечание

В первом примере первый посетитель выбирает окно 1, второй — окно 2, третий встаёт в очередь к окну 2. В момент 2 обслуживание второго посетителя закончилось, и в каждой очереди по одному человеку, поэтому четвёртый посетитель выбирает окно 1. В момент 3 закончилось обслуживание третьего посетителя, в очереди к окну 2 никого нет, и пятый посетитель выбирает его. Окно 2 обслужит троих посетителей.

Во втором примере все посетители приходят одновременно и направляются в окно 1. Первые четверо встают в очередь, остальные шестеро уходят без обслуживания.

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

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

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