08.03.2014, Париж, Франция. Дерзкое ограбление совершено в Парижском музее современного искусства. Похищено множество экспонатов, наиболее известный из которых — картина «Пиксели торжествуют» киберкубиста Этьена Бурсье-Мужено.
«Это большая потеря для нас, — заявил директор музея Фабрис Эрготт. — Полиция уже разыскивает преступников, но мы вынуждены признать, что, судя по тому, как легко злоумышленники справились с охранной системой, мы имеем дело с профессионалами экстра-класса и не питаем надежд на возвращение шедевра в нашу коллекцию. Кроме того, уничтожена вся база данных музея, поэтому реставраторы не обладают достаточным количеством информации для восстановления картины. Безусловно, каждый образованный француз знает, что она представляет собой прямоугольник из \(H\) x \(W\) черных и белых квадратных пикселей (\(H\) — высота, а \(W\) — ширина картины в пикселях). Но информацию о цвете самих пикселей придется добывать по крупицам».
В свою очередь, представитель Национального архива Франции Армель Ле Гофф поспешила успокоить культурную общественность: «К счастью, архив располагает снимками отдельных фрагментов картины. А именно, в нашем распоряжении имеется информация о \(N\) прямоугольных фрагментах (со сторонами, параллельными соответствующим сторонам картины), для каждого из которых известны его координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\), а также цвета входящих в него пикселей. Строки картины пронумерованы от 1 до \(H\) сверху вниз, столбцы — от 1 до \(W\) слева направо, (\(r_1\); \(c_1\)) — номера строки и столбца левого верхнего пикселя фрагмента, (\(r_2\); \(c_2\)) — номера строки и столбца правого нижнего пикселя фрагмента, \(r_1\) ≤ \(r_2\), \(c_1\) ≤ \(c_2\). Однако, в силу ряда причин некоторые фрагменты могут храниться в инвертированном виде, то есть все белые пиксели в них заменены на черные, а все черные — на белые, при этом достоверно не известно, какие фрагменты инвертированы. Это серьезно усложняет задачу по восстановлению утерянного шедевра величайшего киберкубиста, поэтому мы обращаемся за помощью ко всему программистскому сообществу. Национальный архив, со своей стороны, готов предоставить все имеющиеся данные о фрагментах картины. Мы отдаем себе отчет в том, что, возможно, картину не удастся восстановить однозначно, поэтому просим найти максимально светлую из всех возможных подходящих картин, то есть содержащую как можно больше белых пикселей: широко известно, что „Пиксели“ являются одним из самых оптимистичных творений Этьена Бурсье-Мужено».
Первая строка входного файла содержит два целых числа \(H\) и \(W\) (1 ≤ \(H\) * \(W\) ≤ \(10^6\)) — высоту и ширину картины в пикселях. Вторая строка содержит единственное целое число \(N\) (1 ≤ \(N\) ≤ \(10^6\)) — количество фрагментов. Далее содержатся \(N\) описаний фрагментов. Первая строка описания — координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\) (1 ≤ \(r_1\) ≤ \(r_2\) ≤ \(H\), 1 ≤ \(c_1\) ≤ \(c_2\) ≤ \(W\)). Следующие \(r_2\) - \(r_1\) + 1 строк описания содержат сам фрагмент (возможно, инвертированный): каждая из этих строк состоит из ровно \(c_2\) - \(c_1\) + 1 нулей и единиц, разделенных пробелами. Нули означают белые пиксели, единицы - черные.
Суммарная площадь всех фрагментов \(S\) ≤ \(10^6\).
Если подходящей картины не существует, то~есть предоставленные Национальным архивом данные противоречивы, выведите единственное число \(-1\).
Иначе в первой строке выходного файла выведите максимальное число нулей, которое могла содержать утерянная картина, а в следующих \(H\) строках — искомую картину с максимально возможным количеством нулей в том же формате, что и фрагменты во входном файле: \(H\) строк, в каждой из которых \(W\) разделенных пробелами нулей и единиц. Если подходящих картин с максимальным числом белых пикселей несколько, выведите любую из них.
В первом тесте из условия максимально возможное количество белых пикселей равно 5. А именно, нужно инвертировать второй и третий фрагменты, а единственный пиксель, не покрытый фрагментами, покрасить в белый цвет:
Тесты к этой задаче состоят из четырех групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–27. В тестах этой группы \(N\) ≤ 10, \(S\) ≤ 1 000, \(H\) * \(W\) ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 28–36. В тестах этой группы \(N\) ≤ 500, \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
3. Тесты 37–39. В тестах этой группы \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 4 балла, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 36 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой, второй и третьей групп. Тесты в этой группе оцениваются независимо.
2 3 3 1 1 1 2 0 1 1 2 2 2 0 1 1 3 2 3 1 1
5 0 1 0 0 0 0
2 3 2 1 2 2 3 0 1 1 0 1 1 1 3 0 1 1
-1
На улице уже неделю лил беспросветный дождь, а Игорь все сидел дома и играл в свои любимые игрушки. Но играть так долго в одно и то же ему быстро надоело, и он пошел к родителям выпрашивать новые. Родители быстро сдались, поэтому на следующий день вся семья собралась, и они поехали в магазин игрушек.
При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.
Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.
Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.
Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.
Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.
В первой строке содержится натуральное число \(N\) (1 ≤ \(N\) ≤ 100 000) - количество игрушек. Далее следуют описания \(N\) выпуклых многоугольников в следующем формате: сначала идет натуральное число \(k_m\) (3 ≤ \(k_m\) ≤ 300 000) - количество вершин в \(m\)-м многоугольнике, затем идут \(k_m\) строк, в которых записаны пары целых чисел xm,s, ym,s, по модулю не превосходящих \(10^9\) - координаты вершин \(m\)-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что ym,s >= 0, а также для всех игрушек существует вершина \(v_m\), у которой ym,\(v_m\) = 0). Сумма всех \(k_m\) (обозначим ее за \(S\)) не превосходит 300 000.
В следующей строке записано натуральное число \(Q\) (1 ≤ \(Q\) ≤ 500 000) - число вариантов. Следующие \(Q\) строк содержат пары натуральных чисел \(i_t\), \(j_t\) (1 ≤ \(i_t\) < \(j_t\) ≤ \(N\)) - номера сдвигаемых игрушек в очередном варианте.
Выведите \(Q\) строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более \(10^{-9}\).
Верхний рисунок иллюстрирует исходное размещение игрушек в коробках, а нижние — варианты итогового расположения игрушек (оптимальный вариант слева).
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–20. В тестах этой группы \(k_m\) ≤ 100, \(Q\) ≤ 1 000, \(S\) ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.
2. Тесты 21–40. В тестах этой группы \(k_m\) ≤ 300, \(Q\) ≤ 50 000, \(S\) ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.
3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
2 5 0 0 4 2 6 6 3 8 -2 4 5 0 0 2 0 8 4 5 11 3 12 1 1 2
14.5000000000
2 3 0 0 0 3 -1 1 3 0 0 1 0 -20 20 1 1 2
21.0000000000
Еще только начался март, а студент первого курса НУОП (Неизвестного университета олимпиадного программирования) Вениамин уже закрыл сессию — чем не повод устроить вечеринку?
Вениамин назначил день и час, пригласил всех своих друзей и заказал огромное количество пиццы. Он выбирал какую-нибудь новую настольную игру, которую никто из его друзей еще не видел, когда произошло неприятное событие — пиццу доставили гораздо раньше, чем планировалось. Так как к приходу друзей пицца уже гарантированно остынет, необходимо заранее продумать организацию процесса ее разогрева. Теория расписаний изучается в НУОП только на третьем курсе, так что Вениамин обращается к вам за помощью, разумеется, предварительно строго сформулировав задачу:
* Всего у Вениамина имеется N пицц.
* Его цель — выбрать такой порядок разогревания пицц в микроволновке, чтобы в некоторый момент времени как можно больше пицц оказались горячими.
Каждая пицца характеризуется ровно двумя параметрами \(a_i\) и \(b_i\):
– \(a_i\) обозначает время в секундах, необходимое для разогрева \(i\)-й пиццы в микро- волновой печи;
– \(b_i\) обозначает время в секундах, в течение которого пицца остается горячей
* Для разогревания пицц можно использовать только микроволновку, которая у Вениамина ровно одна. Чтобы пицца стала горячей, она должна находится в микроволновке непрерывный отрезок времени длительностью ровно \(a_i\) секунд.
* В каждый момент времени в микроволновке может находиться не более одной пиццы
* Можно считать, что все действия по управлению микроволновкой Веня совершает мгновенно (включить или выключить микроволновку, достать или убрать пиццу).
* Также можно считать, что поедание пицц происходит моментально. Иными словами, нужно добиться того, чтобы максимальное количество пицц было горячими в какой- то момент времени, не обязательно в некий промежуток ненулевой длины.
В первой строке входных данных записано целое число \(N\) — количество пицц (1 ≤ \(N\) ≤ 300 000). Следующие \(N\) строк содержат описания пицц, каждое из которых состоит из двух целых чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ \(10^{9}\)).
Выведите единственное число — максимальное количество пицц, которые могут одновременно оказаться горячими
Разберем подробнее первый тест из условия:
* В нулевой момент времени Вениамин убирает в микроволновку первую пиццу.
* В момент времени 1 Вениамин достает из микроволновки первую пиццу и кладет туда вторую.
* В момент времени 2 Веня достает из микроволновки вторую пиццу, в этот момент первая пицца еще горячая, следовательно, ответ на задачу — 2. Обратите внимание, что две пиццы будут горячими только в этот момент времени, и добиться того, чтобы они были горячими в течение ненулевого по длине промежутка времени, в данном примере невозможно.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–15. В тестах этой группы \(N\) ≤ 10. Эта группа оценивается в 20 баллов.
2. Тесты 16–30. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов.
3. Тесты 31–45. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
2 1 1 1 1
2
4 2 12 10 8 7 5 5 1
3