Что спрашивают

Раздел памяти вместимостью K в начале пуст. Если следующий запрос не помещается, сначала создаётся копия текущего содержимого и очищается раздел, затем записывается запрос. Время копии — время вызвавшего её запроса. При точном заполнении и в конце журнала копия не создаётся.

Найдите клиента с наибольшим объёмом за весь день и сумму двух наибольших копий не позднее 11:59:59. Ввод: N, K, затем время, клиент, объём. N ≤ 100 000, K < 10^6, каждый объём < K; времена в сутках различны. Лидер единственный, ранних копий хотя бы две.

Приём решения

Время ЧЧ:ММ:СС преобразуем в секунды: h * 3600 + m * 60 + s. Запросы сортируем по времени. Сумму каждого клиента считаем по всем строкам, включая вторую половину дня: этот ответ не ограничен утренней границей.

В проходе хранится used — занятый объём перед очередным запросом. Только при used + size > K создаётся копия объёма used; после этого used обнуляется и к нему прибавляется size текущего запроса. При равенстве копирования нет.

Если время копии не больше 43199 секунд, включим её в два наибольших объёма first и second. Новый объём не меньше first сдвигает прежний first во second. Иначе, если новый объём больше second, он заменяет second. Равные объёмы — разные копии, поэтому обе могут войти в сумму.

Порог относится к моменту копирования, а не к времени сохранённых в копии данных. Не добавляйте остаток раздела после последней строки. Время O(N log N), память O(N) на запросы и суммы клиентов; два максимума занимают O(1).

Разбор на примере

Ввод

8 10
12:00:00 7 2
02:00:00 8 4
20:00:00 7 9
05:00:00 7 2
01:00:00 7 6
11:59:59 9 9
03:00:00 7 3
04:00:00 8 6

Вывод

7 19
Разбор примера по шагам
Время запросаКопия перед записьюЗанято после записи
01:00:00Нет6
02:00:00Нет: точное заполнение10
03:00:0010, учитывается3
04:00:00Нет9
05:00:009, учитывается2
11:59:592, учитывается9
12:00:009, уже поздно2
20:00:002, уже поздно9; финальной копии нет

В 02:00 раздел заполняется ровно до 10 без копирования. Утренние копии создаются в 03:00 объёмом 10, в 05:00 объёмом 9 и в 11:59:59 объёмом 2. Две наибольшие дают 19. Копия в 12:00 уже не учитывается. Клиент 7 передал за сутки 22, клиент 8 — 10, клиент 9 — 9; лидер 7.

Код на Python и C++

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

В C++ время hh:mm:ss разбирает sscanf(text.c_str(), "%d:%d:%d", &h, &m, &s), а суммы клиентов лежат в map. Лидер по условию единственный, поэтому порядок перебора клиентов не важен.

import sys


def solve(capacity, records):
    totals = {}
    for time, client, size in records:
        totals[client] = totals.get(client, 0) + size
    used = first = second = 0
    for time, client, size in sorted(records):
        if used + size > capacity:
            if time <= 11 * 3600 + 59 * 60 + 59:
                if used >= first:
                    first, second = used, first
                elif used > second:
                    second = used
            used = 0
        used += size
    return max(totals, key=totals.get), first + second


if __name__ == '__main__':
    stream = sys.stdin
    n, capacity = map(int, stream.readline().split())
    records = []
    for _ in range(n):
        time, client, size = stream.readline().split()
        h, m, s = map(int, time.split(':'))
        records.append((h * 3600 + m * 60 + s, int(client), int(size)))
    print(*solve(capacity, records))
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int n;
    long long capacity;
    cin >> n >> capacity;
    vector<tuple<long long, long long, long long>> records(n);
    map<long long, long long> totals;
    for (auto& [time, client, size] : records) {
        string text;
        cin >> text >> client >> size;
        int h, m, s;
        sscanf(text.c_str(), "%d:%d:%d", &h, &m, &s);
        time = h * 3600 + m * 60 + s;
        totals[client] += size;
    }
    long long leader = 0, best = -1;
    for (auto [client, total] : totals) {
        if (total > best) {
            best = total;
            leader = client;
        }
    }
    sort(records.begin(), records.end());
    long long used = 0, first = 0, second = 0;
    for (auto [time, client, size] : records) {
        if (used + size > capacity) {
            if (time <= 11 * 3600 + 59 * 60 + 59) {
                if (used >= first) {
                    second = first;
                    first = used;
                } else if (used > second) {
                    second = used;
                }
            }
            used = 0;
        }
        used += size;
    }
    cout << leader << ' ' << first + second << endl;
}

Типичные ошибки

  • Копировать при точном заполнении

    Равенство used + size == K лишь заполняет раздел. Копирование произойдёт перед следующим не помещающимся запросом.

  • Взять последние две ранние копии

    Нужны две наибольшие по объёму, а не ближайшие к полудню. В примере последняя ранняя копия 2 не входит в ответ.

  • Ограничить суммы клиентов утром

    Наибольший переданный объём ищется за все сутки. Порог времени применяется только к копиям.

  • Дописать копию в конце

    После последней строки раздел не копируется автоматически. Такая копия не предусмотрена процедурой.