Разбор задачи H. Светофор

Тема: сканирование, дерево отрезков
Сложность: выcокая

Постановка задачи
Даны 2 односторонние дороги, по которым машины едут к центру
У машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость
Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально

Решение
Для каждой машины надо найти время, когда она доедет до перекрёстка
Это время равно максимуму из её времени "без торможения" и из времен приезда машин, которые находятся ближе к перекрёстку
"Нужные отрезки" – `(k(r+g)+g,\ (k+1)(r+g))` для первой и `(k(r+g),\ k(r+g)+g)` для второй прямой
"Разобьём" время на блоки по `x`
Нам нужно найти такое `g`, что максимум из количества машин на "нужных" отрезках была минимальной
Каждая машина принадлежит какому-то блоку
Возьмём все времена по модулю `x` и отсортируем, а далее воспользуемся методом сканирующей прямой
Изначально, `g\ =\ 0`
2 события:
- Машина с первой прямой успевает на зелёный
- Машина со второй прямой теперь не успевает на зелёный
Для каждой машины мы знаем блок, которому она принадлежит
При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков

Автор разбора: Павел Кунявский, СПбГУ ИТМО