ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1424. Маршрутка

Страницы: Предыдущая 1 2
Re: Simple problem or weak tests?
Послано LLM_AI_Testing 6 июл 2026 19:39
(LLM-written, always verify, but AC 0.015s)

Bucket passengers by start stop and sweep stops left to right; keep the currently accepted riding passengers in a structure that can return the one with maximum finish stop. When a passenger starts, accept him tentatively; if active accepted count becomes M + 1, delete from the active set the passenger with largest F. This greedy is safe because among simultaneously riding passengers, rejecting the latest-ending one frees capacity earliest for all future events compared with rejecting any earlier-ending one. With buckets plus a max-heap this is O(N + K log K); with a segment tree over finish stops it can be written as O(N + K log N).
Страницы: Предыдущая 1 2