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

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

Приходы обрабатываются по времени, при равенстве в исходном порядке. Завершившиеся ровно к приходу уже ушли. Найдите число обслуженных окном 2 и число отказов. N ≤ 100 000; обслуживание длится от 1 до 10 000.

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

В каждой очереди храним времена завершения обслуживания уже принятых посетителей. Они строго возрастают: обслуживание последовательное, длительности положительны. Удобна deque с быстрым удалением первого элемента.

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

Иначе время нового завершения равно max(t, последнее завершение очереди) + duration. Для пустой очереди обслуживание начинается в t. Каждый принятый в окно 2 сразу увеличивает его счётчик: по условию все вставшие в очередь будут обслужены.

Сортировка только по времени в Python стабильна, поэтому сохраняет исходный порядок равных приходов. Каждый элемент удаляется один раз. Время O(N log N), память O(N) на вход и сортировку; сами очереди содержат не более восьми времён.

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

Ввод

9
10 1 0
0 10 1
0 10 1
0 10 1
0 10 1
0 1 1
0 1 0
3 1 2
1 2 0

Вывод

4 1
Разбор примера по шагам
ПриходОчереди перед выборомДействие
0, первые четыре вида 1Окно 1: от 0 до 3Завершения 10, 20, 30, 40
0, пятый вида 14 и 0Отказ
0, вид 04 и 0Окно 2 до 1
1, вид 04 и 0Окно 2 до 3
3, вид 24 и 0Окно 2 до 4
10, вид 03 и 0Окно 2 до 11

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

Код на Python и C++

Не сортируйте полные тройки: при одинаковом времени это изменит порядок по длительности и виду услуги. Ключ сортировки содержит только время.

В C++ sort не сохраняет порядок равных элементов, поэтому для сортировки по времени нужен stable_sort. Очереди — deque<long long>.

from collections import deque
import sys


def solve(visitors):
    queues = [deque(), deque()]
    served2 = rejected = 0
    for time, duration, kind in sorted(visitors, key=lambda row: row[0]):
        for queue in queues:
            while queue and queue[0] <= time:
                queue.popleft()
        if kind:
            window = kind - 1
        else:
            window = 0 if len(queues[0]) <= len(queues[1]) else 1
        queue = queues[window]
        if len(queue) == 4:
            rejected += 1
            continue
        start = max(time, queue[-1]) if queue else time
        queue.append(start + duration)
        if window == 1:
            served2 += 1
    return served2, rejected


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    visitors = list(zip(data[1::3], data[2::3], data[3::3]))
    print(*solve(visitors))
#include <algorithm>
#include <deque>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<tuple<long long, long long, int>> visitors(n);
    for (auto& [time, duration, kind] : visitors)
        cin >> time >> duration >> kind;
    // stable_sort сохраняет исходный порядок людей, пришедших одновременно.
    stable_sort(visitors.begin(), visitors.end(),
                [](const auto& x, const auto& y) { return get<0>(x) < get<0>(y); });
    deque<long long> queues[2];
    int served2 = 0, rejected = 0;
    for (auto [time, duration, kind] : visitors) {
        for (auto& queue : queues) {
            while (!queue.empty() && queue.front() <= time)
                queue.pop_front();
        }
        int window;
        if (kind)
            window = kind - 1;
        else
            window = queues[0].size() <= queues[1].size() ? 0 : 1;
        deque<long long>& queue = queues[window];
        if (queue.size() == 4) {
            rejected += 1;
            continue;
        }
        long long start = queue.empty() ? time : max(time, queue.back());
        queue.push_back(start + duration);
        if (window == 1)
            served2 += 1;
    }
    cout << served2 << ' ' << rejected << endl;
}

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

  • Не считать обслуживаемого в очереди

    Ограничение четыре включает человека у окна. Длина deque уже учитывает его.

  • Сначала поставить нового, потом удалить ушедших

    Завершение в момент t происходит до выбора новым посетителем. Сначала удалите все времена не больше t.

  • Выбирать по ближайшему освобождению

    Для вида 0 сравниваются числа людей, а не суммарное ожидание. При равенстве выбирается окно 1.