Сейсмическая тревога
После сильного землетрясения сейсмологи ждут повторных толчков и объявляют в регионе режим наблюдения. Чем сильнее толчок, тем дольше режим. Новый толчок в том же регионе может режим продлить, а дежурный может снять его досрочно. Диспетчерской нужен журнал: когда и в каком регионе режим закончился сам, без отмены.
События идут по времени. Землетрясение Q t r d в регионе r в момент t требует, чтобы режим в регионе действовал хотя бы до момента t + d: если режима нет, он начинается; если он кончается раньше, его продлевают до t + d; если позже — ничего не меняется. Отмена C t r снимает режим в регионе r, если он идёт. Режим, который кончается в момент e, заканчивается раньше всех событий момента e: толчок в тот же момент открывает в регионе новый режим, а отмена в тот же момент уже ничего не снимает.
Один из тестов — настоящий каталог USGS: 19 073 землетрясения силой от 5 за 2015–2025 годы. Регион — клетка 10° × 10° по широте и долготе, время — в секундах от начала 2015 года, а режим длится двое суток после толчка силой 5 и вчетверо дольше за каждую следующую единицу магнитуды.
Вход
В первой строке n (1 ≤ n ≤ 100 000) — число событий. Дальше n строк, каждая — Q t r d или C t r, где 0 ≤ t ≤ 10⁹, 1 ≤ r ≤ 10⁹, 1 ≤ d ≤ 10⁹. Моменты t не убывают.
Выход
Для каждого режима, который закончился сам, — строка e r: момент конца и номер региона. Строки — по возрастанию e, при равных e — по возрастанию номера региона. Режимы, которые ещё идут после последнего события, тоже заканчиваются сами в свои моменты — их выведите тоже. Если таких режимов нет, ничего не выводите.
Примеры
Пример 1
7 Q 0 7 100 Q 30 3 50 Q 60 7 100 C 70 3 Q 75 3 10 Q 90 5 20 Q 100 5 5
85 3 110 5 160 7
Пример 2
6 Q 0 2 10 Q 0 1 10 Q 10 2 5 Q 12 9 3 Q 15 4 1 C 15 9
10 1 10 2 15 2 15 9 16 4
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Режим может продлеваться много раз. Сколько записей о нём держать и что делать со старой записью, когда конец сдвинулся? Искать её не обязательно.
2Подсказка 2
Держите кучу пар (конец, регион) и словарь «регион → текущий конец режима». Когда пара всплывает наверх, как понять, что она ещё что-то значит?
3Идея
Это календарь событий с ленивым удалением. При каждом продлении в кучу ложится новая пара, а старая остаётся лежать. Отмена только стирает регион из словаря. Пара актуальна, если её конец совпадает с текущим концом режима в словаре; продлённые и отменённые режимы этой проверки не проходят, и их пары выбрасываются, когда всплывают. Перед каждым событием достаём из кучи все пары с концом не позже момента события — это режимы, которые закончились раньше него.
4Разбор
Порядок действий на каждом событии: сначала закрыть всё, что кончилось к моменту t, потом применить само событие. Так условие «режим кончается раньше событий своего момента» выполняется само собой. Пары сравниваются сначала по концу, потом по региону, поэтому из кучи они выходят ровно в том порядке, в каком их надо печатать. После последнего события закрываем всё, что осталось.
Проверки «конец совпадает» достаточно. У продлённого режима конец в словаре стал больше, у отменённого записи в словаре нет. Бывает, что режим отменили и тут же открыли снова с тем же концом — тогда в куче две одинаковые пары; первая печатается и стирает регион, вторая уже не находит его в словаре.
Если прочитать все события заранее, можно обойтись и без кучи: пройти по ним, вычислить для каждого режима момент конца и отсортировать концы. Куча нужна, когда журнал надо вести по ходу дела, не зная будущих событий, — как в настоящей диспетчерской.
4+Решение
5Сложность
Каждое землетрясение кладёт в кучу не больше одной пары, каждая пара один раз достаётся: O(n log n) времени и O(n) памяти.
6Типичные ошибки
- Не проверять, актуальна ли пара. Продлённый режим тогда «кончается» дважды. В первом примере такое решение напечатает лишние строки 80 3 и 100 7.
- Сначала событие, потом закрытие. Во втором примере режим региона 2 кончается в момент 10, и толчок в тот же момент должен открыть новый режим, а не продлить старый.
- Перебирать все режимы перед каждым событием. Ответы верны, но в пятом тесте одновременно идут 40 000 режимов, и перебор стоит около миллиарда операций.
- Забыть про равные концы. Режимы, кончившиеся в один момент, печатаются по номеру региона; пары (конец, регион) в куче дают этот порядок даром.