Задача №111621. Конфеты
На кондитерской фабрике работает загадочная машина. Она производит вкусные конфеты, причем каждая из них немного отличается от других. Машина имеет ряд отверстий, занумерованных от \(1\) до \(N\), из которых выпадают приготовленные конфеты. Никто толком не знает, как работает загадочная машина, но перед началом изготовления очередной порции конфет она распечатывает лист, на котором написано, из какого отверстия какая конфета выпадет.
Владелец фабрики хочет разработать систему вагонеток, которые будут перемещаться вдоль машины и ловить выпадающие конфеты. Поскольку конфеты эксклюзивные, ронять их на пол ни в коем случае нельзя.
Вагонетки также недешевое удовольствие и владелец фабрики хочет минимизировать их количество. Напишите программу, которая определяет минимально необходимое количество вагонеток. Вагонетки за одну секунду могут переместиться к соседнему отверстию. Перед началом производства каждая вагонетка может быть поставлена на позицию, в которой она должна поймать первую конфету.
Первая строка содержит целое число \(N\) (\(1 \leq N \leq 100 000\)) — количество конфет, которое будет произведено. Каждая из следующих \(N\) строк содержит пару целых чисел \(S_i\) и \(T_i\) (\(1 \leq S_i, T_i \leq 1\,000\,000\,000\)) — номер отверстия и время, в которое конфета выпадет из него. Из одного отверстия одновременно не может выпадать двух конфет.
Выведите число \(W\) — минимально необходимое количество вагонеток.
В этой задаче есть 3 подзадачи
- Тест 1 (0 баллов). Это тест из условия
- Тесты 2-30 (20 баллов). В этой подзадаче \(N \leq 85\), \(W \leq 4\)(ответ не превосходит четырех)
- Тесты 31-82 (40 баллов). В этой подзадаче \(N \leq 8000\).
- Тесты 81-137 (40 баллов). В этой подзадаче дополнительные ограничения отсутствуют.
5 1 1 2 3 1 5 3 4 2 6
2