Темпоральные дожди

Автор задачи: Артемий Блинов, разработчик: Егор Юлин

Будем решать задачу следующим образом:

Заведём СНМ, в котором будем хранить следующую информацию: количество ячеек в множестве, максимальную высоту $$$d_{i,j}$$$, соприкасается ли хотя бы одна из ячеек с границей.

Отсортируем ячейки по высоте $$$h_{i,j}$$$ и будем обрабатывать их по возрастанию высот. Пусть мы рассматриваем ячейку $$$(i,j)$$$. Рассмотрим все соседние для нее, обозначим такие ячейки за $$$(i',j')$$$. Для них верно, что $$$|i-i'|+|j-j'|=1$$$. Если соседняя еще не была обработана то пропустим её.

Теперь есть два случая:

  1. Если в СНМ для $$$(i',j')$$$ достижима граница, то высота никак не изменится, так как там уже установился максимально доступный уровень энергии, а вся остальная энергия будет просто переливаться через край.
  2. Если в СНМ для $$$(i',j')$$$ граница не достижима, то текущее множество вершин из компоненты $$$(i',j')$$$ ограничено высотой хотя бы $$$h_{i,j}$$$ (ведь иначе мы обработали эти ячейки раньше). Тогда высота каждой ячейки изменится на $$$h_{i,j} - d_{i',j'}$$$. После этого нужно для всех ячеек компоненты установить $$$d$$$, равное $$$h_{i,j}$$$.

После обработки ячейки $$$(i,j)$$$ ее нужно объединить со всеми ячейками $$$(i',j')$$$.

В сумме решение потребует $$$\mathcal{O}(nm \log{nm})$$$ времени как минимум на сортировку по высоте. Работа с СНМ займет асимптотически меньше времени.