Codeforces Round 950 (Div. 3) |
---|
Закончено |
Это усложнённая версия задачи, она отличается от упрощённой только поставленным вопросом.
Алиса и Боб делят поле. Поле представляет собой прямоугольник $$$n \times m$$$ ($$$2 \le n, m \le 10^9$$$), строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$m$$$ слева направо. Клетка на пересечении строки $$$r$$$ и столбца $$$c$$$ обозначается как ($$$r, c$$$).
У Боба есть $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) фонтанов, все из них расположены в разных клетках поля. Алиса отвечает за разделение поля, но должна соблюсти несколько условий:
Алиса хочет разделить поле так, чтобы получить как можно больше клеток.
Боб хочет сохранить владение всеми фонтанами, но один любой из них подарить Алисе. Выведите сначала целое число $$$\alpha$$$ — максимальный возможный размер участка Алисы, если Боб не подарит ей ни один фонтан (т.е. все фонтаны останутся на участке Боба).
Далее выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где $$$a_i$$$ это такое значение, что после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный размер её участка будет равен $$$\alpha + a_i$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 10^9$$$, $$$2 \le k \le 2 \cdot 10^5$$$) — размеры поля и количество фонтанов, соответственно.
Далее следуют $$$k$$$ строк, содержащие по два числа $$$r_i$$$ и $$$c_i$$$ ($$$1 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) — координаты клетки с $$$i$$$-м фонтаном. Гарантируется, что все клетки различны и среди них нет ($$$n, 1$$$).
Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных сначала выведите $$$\alpha$$$ — максимальный размер участка, который может принадлежать Алисе, если Боб не подарит ей ни один из фонтанов. В следующую строку выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где $$$a_i$$$ это такое значение, что после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный размер её участка будет равен $$$\alpha + a_i$$$.
52 2 31 11 22 25 5 41 22 23 44 32 5 91 21 51 12 22 42 51 42 31 36 4 46 21 31 41 23 4 52 13 21 41 32 4
1 1 0 1 11 0 1 0 4 1 0 0 1 1 0 0 0 0 0 6 15 0 0 0 1 2 3 0 0 0
Ниже приведены изображения для второго примера:
Обратите внимание, что если Боб дарит Алисе фонтан $$$1$$$ или фонтан $$$3$$$, то этот фонтан не может находиться на участке Алисы.
Название |
---|