Защищенная тюрьма

Автор задачи и разработчик: Даниил Орешников

По условию, ни один из разрешенных типов комнат не помещается внутри другого. Значит, если комната $$$i$$$-го типа имеет размеры $$$a_i \times b_i$$$, то для любой другой комнаты $$$j$$$-го типа ($$$j \neq i$$$) верно, что либо $$$a_j < a_j$$$, либо $$$b_i < b_j$$$, но не оба неравенства одновременно. Из этого следует, что или $$$a_j < a_i$$$ и $$$b_j \geqslant b_i$$$, или $$$a_i \geqslant a_j$$$ и $$$b_j < b_i$$$. В том и в другом случае нам достаточно расширить только один из размеров комнаты. Давайте для каждого из $$$i$$$ типов рассмотрим оба случая отдельно и в конце выберем тот размер, за изменение которого придется заплатить меньше.

Пусть размеры комнаты $$$i$$$-го типа по-прежнему $$$a_i \times b_i$$$. Рассмотрим такое множество типов комнат $$$J$$$, для которых верно, что $$$a_j < a_i$$$, а тогда $$$b_j \geqslant b_i$$$ для любого $$$j \in J$$$. Чтобы разместить комнату типа $$$j$$$ в комнате $$$i$$$ необходимо как минимум увеличить размер $$$a_j$$$ до $$$a = a_i$$$. При этом $$$b_j$$$ можно не менять, то есть $$$b = b_j$$$. За это придется заплатить как минимум $$$(a + b) - (a_j + b_j) = a_i - a_j$$$ денег.

Чтобы найти такой тип комнат $$$j \in J$$$, за расширение которого до размеров комнаты $$$i$$$-го типа необходимо заплатить минимальное количество денег, нужно выбрать $$$j$$$ с максимальным $$$a_j$$$. Действительно, в таком случае $$$ a_i - a_j$$$ будет минимальным.

Давайте расположим все типы комнат в порядке неубывания их $$$b_k$$$ (и возрастания их $$$a_k$$$, соответственно). Тогда для любого типа комнат $$$i$$$ типы комнат $$$j \in J$$$, то есть те, у которых можно увеличить первый размер, чтобы комнату типа $$$i$$$ разместить внутри комнаты типа $$$j$$$, находятся строго после комнаты $$$i$$$. Тогда задача поиска максимального $$$a_j$$$ для $$$j \in J$$$ равносильна поиску максимума $$$a_k$$$ на суффиксе отсортированного массива типов комнат. Причем этот суффикс начинается сразу после позиции на которой расположен $$$i$$$-й тип комнат.

Давайте отсортируем типы комнат в указанном порядке. Затем поcчитаем максимумы $$$a_k$$$ на всех суффиксах массива типов комнат (это делается за один проход с конца массива). Теперь снова пройдем по массиву (в этот раз можно с начала) и для каждого типа комнат $$$i$$$ запомним максимум на суффиксе в массив $$$\mathtt{ans}_a[i]$$$. Напоминаем, он равен $$$\mathtt{suff}[pos(i) + 1]$$$, где $$$pos(i)$$$ — порядковый номер комнаты в отсортированном массиве. Для комнаты, стоящей последней в отсортированном массиве, максимум на суффиксе будет не определен, будем считать, что $$$\mathtt{ans}_a[i] = +\infty$$$.

Далее проделаем аналогичную последовательность действий, но для второй стороны: отсортируем по возрастанию $$$b_k$$$ (это будет просто обратный порядок); посчитаем суффиксные максимумы; для каждого типа запомним максимум на соответствующем суффиксе в массив $$$\mathtt{ans}_b[i]$$$.

После этого, можно вывести ответ. Если для $$$i$$$-го типа комнат ответ будет равен $$$min\left( a_i - \mathtt{ans}_a[i], b_i - \mathtt{ans}_b[i] \right)$$$. Для такого решения необходимо отсортировать массив типов комнат и несколько раз проитерироваться по нему. Таким образом, время работы — $$$\mathcal{O}(n \log n)$$$.