Олимпиадный тренинг

Задача . D. Андрей и побег из Капиграда

Задача

Темы: Бинарный поиск дп жадные алгоритмы снм сортировки Структуры данных *1800

В Капиграде, столице Тяголяндии, произошло происшествие, все капибары в городе одичали и стали кидаться мандаринами. Андрей был вынужден сбежать из города максимально далеко, пользуясь порталами.

Тяголяндия представляет из себя числовую прямую, а Капиград находится в точке $0$. По всей Тяголяндии расставлены $n$ порталов, каждый из которых характеризуется четырьмя целыми числами $l_i$, $r_i$, $a_i$ и $b_i$ ($1 \le l_i \le a_i \le b_i \le r_i \le 10^9$). Обратите внимание, что отрезок $[a_i, b_i]$ содержится в отрезке $[l_i, r_i]$.

Если Андрей находится на отрезке $[l_i, r_i]$, тогда портал может его телепортировать в любую точку на отрезке $[a_i, b_i]$. У Андрея есть проездной, который позволяет ему пользоваться порталами неограниченное количество раз.

Андрей считает, что точка $x$ находится на отрезке $[l, r]$, если выполняется неравенство $l \le x \le r$.

У Андрея есть $q$ вариантов откуда начать свой побег, каждый вариант характеризуется одним целом числом $x_i$ — позицией начала побега. Он хочет убежать от Капиграда как можно дальше (в точку с максимально возможной координатой). Помогите Андрею узнать, насколько далеко от Капиграда он может убежать, начиная в каждой из $q$ позиций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора данных содержит одно целое число $n$ ($1 \le n \le 2 \cdot 10^5$) — количество порталов.

Каждая из следующих $n$ строк содержит четыре целых числа $l_i$, $r_i$, $a_i$ и $b_i$ $(1 \le l_i \le a_i \le b_i \le r_i \le 10^9)$ — характеристики порталов.

Следующая строка содержит одно целое число $q$ ($1 \le q \le 2 \cdot 10^5$) — количество позиций.

В следующей строке задано $q$ целых чисел $x_1, x_2, \ldots, x_q$ ($1 \le x_i \le 10^9$) — позиция, откуда Андрей начнет свой побег в $i$-м варианте.

Гарантируется, что сумма $n$ и сумма $q$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку из $q$ целых чисел, содержащую ответы на интересующие Андрея вопросы.

Примечание

В первом наборе входных данных:

$\text{[math]}$

Оптимальные действия при старте из каждой позиции:

Воспользуемся порталом $1$ и телепортируемся в точку $b_1 = 14$.
Воспользуемся сначала порталом $2$ и телепортируемся в точку $6$, находящуюся на отрезке $[l_1, r_1] = [6, 17]$, после чего воспользуемся порталом $1$ и телепортируемся в точку $b_1 = 14$.
Останемся в точке $x_3=23$, не пользуясь порталами.
Останемся в точке $x_4=15$, не пользуясь порталами.
Точка $x_5=28$ не находится ни на одном отрезке, поэтому Андрей не сможет никуда телепортироваться.
Точка $x_6=18$ находится на отрезке $[l_3, r_3] = [16, 24]$, воспользуемся порталом $3$ и телепортируемся в точку $b_3 = 22$.

В пятом наборе входных данных:

$\text{[math]}$

Оптимальные действия при старте из каждой позиции:

Воспользуемся сначала порталом $1$ и телепортируемся в точку $15$ на отрезке $[a_1, b_1] = [14, 20]$, после чего воспользуемся порталом $2$ и телепортируемся в точку $21$, находящуюся на отрезке $[l_4, r_4] = [21, 33]$ и на отрезке $[a_2, b_2] = [13, 24]$, после телепортируемся в точку $b_4 = 32$.
Воспользуемся сначала порталом $6$ и телепортируемся в точку $20$ на отрезке $[a_6, b_6] = [20, 21]$, после чего воспользуемся порталом $2$ и телепортируемся в точку $22$, находящуюся одновременно на отрезке $[l_4, r_4] = [21, 33]$ и на отрезке $[a_2, b_2] = [13, 24]$, после телепортируемся в точку $b_4 = 32$.
Сделаем те же самые действия что из с первой позиции.
Останемся в точке $x_4=5$, не пользуясь порталами.
Точка $8$ не находится ни на одном отрезке, поэтому Андрей не сможет никуда телепортироваться.
Останемся в точке $x_6=33$, не пользуясь порталами.
Воспользуемся порталом $5$ и телепортируемся в точку $b_5 = 4$.
Сделаем те же самые действия что и из первой позиции.

Примеры

№	Входные данные	Выходные данные
1	5 3 6 17 7 14 1 12 3 8 16 24 20 22 6 10 2 23 15 28 18 3 3 14 7 10 16 24 20 22 1 16 3 14 9 2 4 6 8 18 23 11 13 15 2 1 4 2 3 3 9 6 7 3 4 8 1 5 18 24 18 24 1 8 2 4 11 16 14 14 26 32 28 30 5 10 6 8 9 15 14 13 27 22 17 31 1 7 6 9 22 14 20 11 26 13 24 21 33 22 23 21 33 25 32 1 6 3 4 18 29 20 21 8 11 23 16 5 8 33 2 21	14 14 23 15 28 22 14 14 14 14 22 23 14 14 15 7 8 7 15 14 14 30 24 17 31 4 8 32 32 32 5 8 33 4 32

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет