Задача №114762. Интересные выходные
Петя и его младший брат Коля пришли в аквапарк. Коля любит кататься с горки, которую можно схематически изобразить как часть треугольной сетки, вершины которой — узлы горки. В каждом узле можно выбрать, по какой трубе ехать дальше — влево-вниз или вправо-вниз.
Уровни горки нумеруются сверху вниз, начиная с \(0\). На нулевом уровне у горки один узел — начало поездки, на первом уровне — два узла, ..., на \(i\)-м уровне — \(i + 1\) узлов. Всего у горки \(n + 1\) уровней. Каждая поездка сверху вниз проходит ровно по \(n\) трубам. У каждого узла есть координаты: два числа \((r, c)\) задают \(c\)-й слева узел на уровне \(r\) (\(0 \leq c \leq r \leq n\)). Обратите внимание, что и уровни, и узлы на каждом уровне нумеруются с \(0\). Если Коля находится в узле \((r, c)\) и поедет влево-вниз, он попадет в узел \((r + 1, c)\), а если он поедет вправо-вниз, он попадет в узел \((r + 1, c + 1)\).
Коля хочет скатиться с горки ровно \(n + 1\) раз. Перед каждым спуском Петя будет выдавать ему инструкцию, как надо спуститься по горке. Каждая инструкция состоит ровно из \(n\) команд «влево-вниз» или «вправо-вниз» — куда Коля должен ехать из очередного узла.
Первая инструкция состоит только из команд «вправо-вниз». Пете лень придумывать новые инструкции, поэтому инструкции для двух соседних спусков отличаются только одной командой: чтобы получить инструкцию \(i + 1\) из инструкции \(i\), надо изменить \(a_i\)-ю команду с «вправо-вниз» на «влево-вниз» (\(1 \leq a_i \leq n\)). Заметим, что каждая команда будет изменена таким образом ровно один раз. В результате, \((n + 1)\)-я инструкция будет состоять только из команд «влево-вниз». Можно показать, что каждый узел будет посещен Колей хотя бы в одном из спусков.
На обратном пути из аквапарка у Коли возникло несколько вопросов следующего вида. Рассмотрим множество всех труб, по которым он проехал хотя бы один раз. Коля называет координаты двух узлов: \((r_1, c_1)\) и \((r_2, c_2)\). Вы должны определить координаты такого узла \((r_3, c_3)\), что из него по рассматриваемым трубам достижимы узлы \((r_1, c_1)\) и \((r_2, c_2)\), и среди всех таких узел \((r_3, c_3)\) является наиболее низким, то есть с максимальным возможным значением \(r_3\). Можно показать, что такой узел всегда существует и единственен.
Ответьте на все его вопросы!
В первой строке дано одно целое число \(n\) (\(1 \leq n \leq 500\,000\)).
В следующей строке даны \(n\) целых чисел \(a_1\), \(a_2\), ... \(a_n\) (\(1 \leq a_i \leq n\)), где \(a_i\) — номер команды, которая изменится после \(i\)-го спуска. Гарантируется, что все \(a_i\) различны.
В следующей строке дано одно целое число \(q\) (\(1 \leq q \leq 500\,000\)) — количество вопросов Коли.
В каждой из следующих \(q\) строк даны четыре целых числа \(r_{i,1}\), \(c_{i,1}\), \(r_{i,2}\) и \(c_{i,2}\) (\(0 \leq r_{i,1}, r_{i,2} \leq n\); \(0 \leq c_{i,1} \leq r_{i,1}\); \(0 \leq c_{i,2} \leq r_{i,2}\)) — координаты первого и второго узлов из \(i\)-го вопроса.
Выведите \(q\) строк, в \(i\)-й строке выведите два целых числа \(r_{i,3}\) и \(c_{i, 3}\) — координаты узла, являющегося ответом на \(i\)-й вопрос.
| Ограничения | ||||||
| Подзадача | Баллы | \(n\) | \(q\) | дополнительно | Необх. подзадачи | Информация о проверке |
| 1 | 14 | \(n \le 300\) | \(q \le 300\) | У | первая ошибка | |
| 2 | 23 | \(n \le 3000\) | \(q \le 3000\) | У, 1 | первая ошибка | |
| 3 | 10 | \(n \le 100\,000\) | \(q \le 100\,000\) | \(a_i = i\) для всех \(i\) | первая ошибка | |
| 4 | 13 | \(n \le 100\,000\) | \(q \le 100\,000\) | массив \(a\) имеет особый вид, см. ниже | первая ошибка | |
| 5 | 15 | \(n \le 100\,000\) | \(q \le 100\,000\) | У, 1–4 | первая ошибка | |
| 6 | 14 | \(n \le 300\,000\) | \(q \le 300\,000\) | У, 1–5 | первая ошибка | |
| 7 | 11 | \(n \le 500\,000\) | \(q \le 500\,000\) | У, 1–6 | первая ошибка | |
В подзадаче 4 массив \(a\) имеет вид \(1, 2, \dots k, n, n - 1, \dots k + 1\) для \(0 \leq k \leq n\).
3 2 3 1 5 3 3 3 0 2 2 2 1 1 0 3 1 3 1 3 2 2 2 2 2
0 0 1 1 0 0 2 1 2 2