| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 212 | 39 | 24 | 21.622% |
Петя и его младший брат Коля пришли в аквапарк. Коля любит кататься с горки, которую можно схематически изобразить как часть треугольной сетки, вершины которой --- узлы горки. В каждом узле можно выбрать, по какой трубе ехать дальше --- влево-вниз или вправо-вниз.
Уровни горки нумеруются сверху вниз, начиная с 0ドル$. На нулевом уровне у горки один узел --- начало поездки, на первом уровне --- два узла, \ldots, на $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)$.
Пример горки в аквапарке с 5 уровнями:
Коля хочет скатиться с горки ровно $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,ドル \ldots $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$-й вопрос.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | $n \le 300,ドル $q \le 300$ |
| 2 | 23 | $n \le 3000,ドル $q \le 3000$ |
| 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円$ |
| 6 | 14 | $n \le 300,000円,ドル $q \le 300,000円$ |
| 7 | 11 | $n \le 500,000円,ドル $q \le 500,000円$ |
В подзадаче 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
В первом примере спуски Коли выглядят следующим образом:
Если отметить все трубы, по которым проехал Коля в первом примере, то получится следующее: