Задача 20 из 21

Резервные копии сервера

Демоверсия 2027Время 2 с · память 256 МБ

Сервер принимает данные от клиентских устройств. Каждый запрос на передачу данных регистрируется в журнале работы сервера: записываются время регистрации, идентификатор клиентского устройства и объём данных. Сами данные сохраняются в специальном разделе памяти вместимостью KK Кбайт; в начале суток раздел пуст.

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

Определите идентификатор клиентского устройства, с которого на сервер передан наибольший общий объём данных, и сумму объёмов (в Кбайт) двух наибольших резервных копий, созданных не позднее 11:59:59.

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

В первой строке находятся два натуральных числа: NN — количество строк в журнале (N≤100 000N \le 100\,000) и KK — вместимость раздела памяти в Кбайт (K<1 000 000K < 1\,000\,000). Каждая из следующих NN строк содержит сведения об одном запросе: время регистрации в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: CC — идентификатор клиентского устройства (C<1 000 000C < 1\,000\,000) и SS — объём данных запроса в Кбайт (S<KS < K). Значения в строке разделены пробелами.

Все запросы относятся к одним суткам, время регистрации у всех запросов разное; строки журнала идут в произвольном порядке. Гарантируется, что наибольший общий объём данных передан только с одного устройства и что не позднее 11:59:59 создано не менее двух резервных копий.

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

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

Примеры

Ввод 1
8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000
Вывод 1
303 220000
Ввод 2
3 3
11:59:59 7 2
11:59:57 7 2
11:59:58 7 2
Вывод 2
7 4

Примечание

В первом примере копии создаются в 05:05:05, 07:07:07, 21:21:21 и 23:23:23 с объёмами 130 000, 90 000, 122 000 и 120 000 Кбайт. До указанной границы созданы первые две копии, их сумма — 220 000 Кбайт. Клиент 303 передал 182 000 Кбайт — больше любого другого клиента.

Во втором примере запросы сначала нужно упорядочить по времени. При выполнении второго и третьего запросов создаются копии по 2 Кбайт. Копия в 11:59:59 учитывается, поэтому сумма равна 4.

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

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

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