| Codeforces Round 1118 (Div. 2) |
|---|
| Закончено |
Magic Tiles — известная во всём мире музыкальная игра, и эта задача основана на ней. Ноян не очень хорошо играет в игры, требующие быстрой реакции и высокой концентрации. Поэтому он может использовать только один палец, то есть нажимать не более одной плитки в каждой строке. Кроме того, когда он несколько раз подряд нажимает плитки в одном столбце, он получает количество очков, зависящее от длины этой серии. Однако если он нажимает неправильную плитку, то проигрывает. Помогите Нояну определить оптимальный выбор плиток, чтобы максимизировать результат.
Дана таблица из $$$10^{18}$$$ строк и $$$2$$$ столбцов. Строки пронумерованы от $$$1$$$ до $$$10^{18}$$$, а столбцы имеют номера $$$1$$$ и $$$2$$$. Каждая ячейка покрашена либо в белый, либо в чёрный цвет.
Вам нужно выбрать подмножество чёрных ячеек так, чтобы в каждой строке было выбрано не более одной ячейки. Ваша цель — максимизировать суммарный счет $$$S$$$, равный сумме счетов, независимо вычисленных для первого и второго столбцов.
Счет для одного столбца определяется как $$$$$$ \sum_{i=1}^{k} 100^{100^{x_i}}, $$$$$$ где $$$k$$$ — количество максимальных по включению непрерывных отрезков выбранных ячеек в этом столбце, а $$$x_i$$$ обозначает длину $$$i$$$-го такого отрезка.
Определите максимально возможный суммарный счет.
Поскольку таблица имеет астрономический размер, входные данные будут заданы в сжатом виде с помощью максимальных по включению чёрных отрезков в каждом столбце. Вам также нужно вывести ответ в сжатом виде. Подробности приведены в разделах входных и выходных данных.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 3000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3000$$$) — количество отрезков чёрных ячеек в столбцах 1 и 2 соответственно.
В следующих $$$n$$$ строках каждого набора входных данных содержатся отрезки чёрных ячеек в столбце 1. В $$$i$$$-й из этих строк содержатся два целых числа $$$l_{1, i}$$$ и $$$r_{1, i}$$$ ($$$1 \le l_{1, i} \le r_{1, i} \le 10^{18}$$$), задающие непрерывный отрезок чёрных ячеек с $$$l_{1, i}$$$-й по $$$r_{1, i}$$$-ю строку включительно.
В следующих $$$m$$$ строках каждого набора входных данных содержатся отрезки чёрных ячеек в столбце 2. В $$$j$$$-й из этих строк содержатся два целых числа $$$l_{2, j}$$$ и $$$r_{2, j}$$$ ($$$1 \le l_{2, j} \le r_{2, j} \le 10^{18}$$$), задающие непрерывный отрезок чёрных ячеек с $$$l_{2, j}$$$-й по $$$r_{2, j}$$$-ю строку включительно.
В пределах одного столбца никакие два заданных отрезка не соприкасаются. Формально, $$$r_{1, i} + 1 \lt l_{1, i+1}$$$ и $$$r_{2, j} + 1 \lt l_{2, j+1}$$$ для всех допустимых $$$i$$$ и $$$j$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$3000$$$.
Для каждого набора входных данных выведите две строки.
В первой строке должно содержаться одно целое число $$$c$$$ ($$$1 \leq c$$$) — суммарное количество максимальных по включению непрерывных выбранных отрезков в обоих столбцах.
Во второй строке должны содержаться $$$c$$$ целых чисел $$$x_1, x_2, \ldots, x_c$$$ — длины всех выбранных отрезков, упорядоченные в порядке невозрастания ($$$x_1 \ge x_2 \ge \ldots \ge x_c \ge 1$$$).
41 11 35 61 11 41 42 21 47 103 79 121 11 10000000000000000001 1
23 21445 4 2 111000000000000000000
В первом наборе входных данных два чёрных отрезка не пересекаются. Выберем строки с $$$1$$$-й по $$$3$$$-ю в первом столбце и строки с $$$5$$$-й по $$$6$$$-ю во втором столбце. Получатся два отрезка длиной $$$3$$$ и $$$2$$$.
Во втором наборе входных данных ячейки обоих столбцов в строках с $$$1$$$-й по $$$4$$$-ю чёрные. Поскольку в каждой строке можно выбрать не более одной ячейки, выберем все четыре ячейки в одном из столбцов. Получится один отрезок длиной $$$4$$$.
В третьем наборе входных данных один из оптимальных способов выбора имеет следующий вид:
- строки $$$1$$$ и $$$2$$$ в первом столбце;
- строки с $$$3$$$-й по $$$7$$$-ю во втором столбце;
- строка $$$8$$$ в первом столбце;
- строки с $$$9$$$-й по $$$12$$$-ю во втором столбце.
Таким образом, выбранные отрезки в первом столбце имеют длины $$$2$$$ и $$$1$$$, а выбранные отрезки во втором столбце — длины $$$5$$$ и $$$4$$$. После сортировки длин всех отрезков в порядке невозрастания ответ равен $$$[5,4,2,1]$$$.
Можно показать, что все приведённые построения оптимальны для соответствующих наборов входных данных.
 |  |  |
| Таблица для первого примера | Таблица для второго примера | Таблица для третьего примера |
На приведённых выше рисунках выбранные ячейки обозначены красным цветом.
