Codeforces Round 754 (Div. 2) |
---|
Закончено |
У Jeevan есть два массива $$$a$$$ и $$$b$$$ размером $$$n$$$. Он любит выполнять странные операции над массивами. На этот раз он придумал два типа операций:
Он хочет преобразовать массив $$$a$$$ в массив $$$b$$$, используя минимальное общее количество операций. Однако Jeevan, похоже, забыл значение $$$b_1$$$. Поэтому он делает некоторые предположения. Он задаст вам $$$q$$$ вопросов, соответствующих его $$$q$$$ догадкам, $$$i$$$-я из которых имеет вид:
Помогите ему, ответив на каждый вопрос.
Первая строка содержит одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — размер массивов $$$a$$$ и $$$b$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^{6})$$$.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, ..., b_n$$$ $$$(1 \le b_i \le 10^6$$$ для $$$i \neq 1$$$; $$$b_1 = -1$$$, что означает, что значение $$$b_1$$$ неизвестно$$$)$$$.
Четвертая строка содержит одно целое число $$$q$$$ $$$(1 \le q \le 2 \cdot 10^{5})$$$ — количество вопросов.
Каждая из следующих $$$q$$$ строк содержит одно целое число $$$x_i$$$ $$$(1 \le x_i \le 10^6)$$$ — представляющее $$$i$$$-й вопрос.
Выведите $$$q$$$ целых чисел — ответы на каждый из его $$$q$$$ вопросов.
2 3 7 -1 5 3 1 4 3
2 4 2
6 2 5 4 1 3 6 -1 4 6 2 3 5 3 1 8 4
10 29 9
Рассмотрим первый пример.
$$$[3, 7]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 1}}$$$ $$$[2, 6]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 1}}$$$ $$$[1, 5]$$$ Следовательно, ответ равен $$$2$$$.
$$$[3, 7]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 2}}$$$ $$$[3, 5]$$$ $$$\xrightarrow[\text{увеличить}]{\text{i = 1}}$$$ $$$[4, 6]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 2}}$$$ $$$[4, 5]$$$
Следовательно, ответ — $$$4$$$.
$$$[3, 7]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{уменьшить}]{\text{i = 2}}$$$ $$$[3, 5]$$$
Следовательно, ответ равен $$$2$$$.
Название |
---|