1. Идея

Нужно обработать журнал событий парковки и посчитать:

• общий доход за смену;
• сколько заплатил каждый автомобиль суммарно по всем своим сессиям.

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

Для каждого автомобиля будем хранить время его последнего въезда. Когда встречаем выезд, сразу можем вычислить длительность стоянки в минутах, округлить её вверх до часов, посчитать стоимость и добавить её:

• в общий доход;
• в сумму для этого номера.

2. Наблюдения

1. Для времени удобно перейти от строки HH:MM к числу минут от начала суток.

   Например:

   • 00:00 → 0
   • 01:15 → 75
   • 23:59 → 1439

2. Если автомобиль стоял minutes минут, то число оплачиваемых часов равно округлению вверх minutes / 60.

   Это удобно считать формулой: hours = (minutes + 59) // 60

   Примеры:

   • 1 минута → (1 + 59) // 60 = 1
   • 60 минут → (60 + 59) // 60 = 1
   • 61 минута → (61 + 59) // 60 = 2

3. Гарантируется корректность журнала:

   • каждый OUT имеет соответствующий предыдущий IN;
   • у одного автомобиля не бывает вложенных въездов;
   • к концу все выехали.

   Поэтому можно хранить только текущее время въезда для машин, которые сейчас на парковке.

4. В выводе автомобили должны идти по возрастанию номера.
   Поэтому:

   • в C++ удобно использовать map, он уже хранит ключи отсортированными;
   • в Python можно накапливать в словаре, а в конце пройти по sorted(cost_by_plate).

3. Алгоритм

1. Считываем n и t.
2. Заводим:
   • enter_time — время въезда автомобилей, которые сейчас стоят на парковке;
   • cost_by_plate — накопленная стоимость для каждого номера;
   • total — общий доход.
3. Для каждого из n событий:
   • читаем time, type, plate;
   • переводим time в минуты;
   • если событие IN:
     • запоминаем время въезда enter_time[plate] = cur_time;
     • если автомобиль раньше не встречался, создаём для него запись в cost_by_plate со значением 0;
   • если событие OUT:
     • берём время въезда;
     • считаем minutes = cur_time - start_time;
     • считаем оплачиваемые часы: hours = (minutes + 59) // 60;
     • стоимость сессии: cost = hours * t;
     • прибавляем cost к total;
     • прибавляем cost к cost_by_plate[plate];
     • удаляем автомобиль из enter_time, потому что он уехал.
4. Печатаем total.
5. Печатаем все пары plate cost в порядке возрастания номера.

4. Почему это работает

Докажем, что алгоритм считает ответ правильно.

Рассмотрим любой автомобиль.

• Когда встречается его событие IN, алгоритм сохраняет точное время въезда.
• По условию между этим въездом и соответствующим выездом нет других событий этого же автомобиля.
• Значит, когда встречается OUT, в enter_time[plate] лежит именно время начала текущей парковочной сессии.

Тогда алгоритм правильно вычисляет длительность этой сессии: minutes = время_выезда - время_въезда.

Дальше по условию оплата берётся за каждый начатый час, то есть нужно округлить число часов вверх. Формула (minutes + 59) // 60 делает именно это, значит стоимость сессии вычисляется верно.

После этого алгоритм:

• добавляет стоимость к общему доходу;
• добавляет её к сумме конкретного автомобиля.

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

Следовательно:

• total равен сумме стоимостей всех сессий;
• cost_by_plate[plate] равен сумме стоимостей всех сессий данного автомобиля.

Значит, алгоритм выводит правильный ответ.

5. Сложность

Пусть n — число событий.

C++

Используется map, поэтому каждая операция чтения, записи или удаления работает за O(log k), где k — число различных автомобилей.

Итоговая сложность:

• O(n log k)

Память:

• O(k)

Python

Словари работают в среднем за O(1) на операцию, а в конце есть сортировка всех автомобилей.

Итоговая сложность:

• обработка событий: O(n)
• сортировка номеров: O(k log k)

Итого:

• O(n + k log k)

Память:

• O(k)

6. Код на C++17

#include <iostream>
#include <string>
#include <map>

using namespace std;

int toMinutes(const string& s) {
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    return h * 60 + m;
}

int main() {
    int n;
    long long t;
    cin >> n >> t;

    map<long long, int> enter_time;
    map<long long, long long> cost_by_plate;
    long long total = 0;

    for (int i = 0; i < n; i++) {
        string time_str, type;
        long long plate;
        cin >> time_str >> type >> plate;

        int cur_time = toMinutes(time_str);

        if (type == "IN") {
            enter_time[plate] = cur_time;
            if (cost_by_plate.find(plate) == cost_by_plate.end()) {
                cost_by_plate[plate] = 0;
            }
        } else {
            int start_time = enter_time[plate];
            int minutes = cur_time - start_time;
            long long hours = (minutes + 59) / 60;
            long long cost = hours * t;
            total += cost;
            cost_by_plate[plate] += cost;
            enter_time.erase(plate);
        }
    }

    cout << total << "\n";
    for (map<long long, long long>::iterator it = cost_by_plate.begin(); it != cost_by_plate.end(); ++it) {
        cout << it->first << " " << it->second << "\n";
    }

    return 0;
}

7. Код на Python 3

n, t = map(int, input().split())

enter_time = {}
cost_by_plate = {}
total = 0

for _ in range(n):
    time_str, typ, plate_str = input().split()
    plate = int(plate_str)

    h = int(time_str[:2])
    m = int(time_str[3:])
    cur_time = h * 60 + m

    if typ == "IN":
        enter_time[plate] = cur_time
        if plate not in cost_by_plate:
            cost_by_plate[plate] = 0
    else:
        start_time = enter_time[plate]
        minutes = cur_time - start_time
        hours = (minutes + 59) // 60
        cost = hours * t
        total += cost
        cost_by_plate[plate] += cost
        del enter_time[plate]

print(total)
for plate in sorted(cost_by_plate):
    print(plate, cost_by_plate[plate])