Задача №115184. Сложная задача
Мальчик Гена очень любит решать сложные задачи по программированию. Недавно он составил себе подборку из \(n\) задач, которые собирается прорешать. Задачи имеют уровни сложности \(a_1,\ a_2,\ \ldots,\ a_n\), причём известно, что у любых двух задачек уровни сложности различны.
Гена очень опытный программист, и поэтому может решить сколь угодно сложные задачи. Гена ежедневно решает задачи, у него есть определенная стратегия, по которой он это делает.
Для каждого дня у Гены зафиксирован свой параметр \(m\) — минимальный уровень сложности задач, которые он готов решать. Каждый день Гена проходится по всем задачам из подборки начиная с первой до последней, и для каждой из них он делает следующее действие:
- Если текущая задача уже была сдана, то он её пропускает и переходит к следующей.
- Если у текущей задачи уровень сложности меньше \(m\), то он её пропускает и переходит к следующей.
- Если условия предыдущих пунктов не выполнились, и в текущий день он не решал задач, то он решает текущую задачу и переходит к следующей.
- Если условия предыдущих пунктов не выполнились, и последняя решенная за день задача была легче текущей, то он решает текущую задачу и переходит к следующей.
- Если условия первых четырех пунктов не выполнились, то Гена пропускает задачу и переходит к следующей.
Проще говоря, Гена каждый день решает задачи в порядке возрастания сложности, но решает только те задачи, которые раньше не решал, и которые по сложности не меньше \(m\).
В первый день минимальная сложность задач, которые он готов решать равна \(t\), а каждый следующий день он будет уменьшать \(m\) на значение \(s\). Таким образом в \(i\)-й день (в нумерации с 1) Гена готов решать задачи сложности не меньше \(t - s \cdot (i - 1)\). Гена будет ежедневно повторять описанный выше алгоритм до тех пор, пока не сдаст все задачи.
Мальчик Леша давно наблюдает за успехами Гены, и хочет узнать секрет его стратегии решения задач. Поэтому у Леши есть \(q\) запросов. Для каждого запроса требуется проверить, можно ли так переставить задачи в подборке Гены, чтобы задачу с уровнем сложности \(d_i\) он сдал \(p_i\)-й по счёту среди всех сданных задач за все дни. Помогите Леше ответить на все его запросы.
Обратите внимание, что запросы независимы , то есть для разных запросов могут использоваться различные порядки задач в подборке Гены.
Первая строка содержит три целых числа \(n\), \(t\), \(s\) (\(1 \le n \le 200\, 000\), \(1 \le t, s \le 10^9\)) — количество задач подборке, минимальный уровень сложности в первый день и шаг понижения уровня сложности задач.
Вторая строка содержит \(n\) различных целых чисел \(a_1,\ a_2,\ \ldots,\ a_n\) (\(1 \le a_i \le 10^9\), \(a_i < a_{i+1}\)) — уровни сложности задач.
Третья строка содержит единственное целое число \(q\) (\(1 \le q \le 200\, 000\)) — количество запросов.
Следующие \(q\) строк содержат по два целых числа \(d_i\) и \(p_i\) (\(1 \le p_i \le n\)) — параметры запроса: можно ли переставить задачи в подборке так, чтобы задача сложности \(d_i\) была сдана \(p_i\)-й по счёту. Гарантируется, что для каждого запроса существует задача в подборке, сложность которой равна \(d_i\).
Для каждого запроса выведите « Yes » (без кавычек), если можно переставить задачи в подборке, чтобы условие запроса выполнялось, и « No » (без кавычек) в противном случае.
Пусть в первом примере для второго запроса можно переставить задачи в подборке в таком порядке: 12, 4, 5, 9, 10. Тогда Гена будет прорешивать задачи следующим образом:
-
В первый день минимальная сложность задач \(m = 10\). Под это условие подходит первая задача в подборке. Гена её сразу решит. Среди следующих задач есть задача сложности 10, но так как Гена уже сдал за первый день задачу сложности 12, то задачу сложности
10 он пропускает. Таким образом после окончания первого дня Гена сдаст только задачу сложности 12.
-
Во торой день минимальная сложность задач \(m = 8\). Во время прохода по задачам из подборке Гена пропустит задачу 12, так как уже сдавал её. Задачи сложности 4 и 5 он пропустит, так как их сложность меньше \(m\). Далее он встретит задачу сложности 9,
и так как за второй день он ещё не сдавал задач, то он сдаст её. Следующей задачей идет задача сложности 10, и так её сложность больше сложности последней сданной за день задачи, то он сдаст её. Таким образом после первых двух дней Гена
сдаст задачи сложности 12, 9, 10 в соответствующем порядке.
-
В третий день Гена не сдаст ни одной задачи, так как все задачи сложности хотя бы \(m = 6 = 10 - 2 \cdot 2\) уже решены.
-
В последний четвёртый день Гена сдаст оставшиеся задачи, итоговая за все дни он сдаст задачи сложности 12, 9, 10, 4, 5 в соответствующем порядке.
При данной перестановке задач в подборке Гена сдаст задачу сложности 10 третьей по счёту среди всех, поэтому ответ на второй запрос « Yes ».
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(q\) | \(a_i\) | \(t\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия |
| 1 | 13 | \(n \le 8\) | – | \(a_i \le 10\) | \(t \le 10\) | – | |
| 2 | 10 | \(n \le 8\) | – | – | – | 0, 1 | |
| 3 | 14 | \(n \le 500\) | – | – | \(t \le 10\) | \(0,1\) | |
| 4 | 19 | \(n \le 500\) | – | – | – | 0 – 3 | |
| 5 | 9 | – | \(q=1\) | – | – | – | |
| 6 | 1 | – | – | – | \(t=1\) | – | |
| 7 | 9 | – | – | – | – | – | \(s=10^9\) |
| 8 | 25 | – | – | – | – | 0 – 7 | |
5 10 2 4 5 9 10 12 5 10 2 10 3 10 4 5 5 12 2
Yes Yes No Yes Yes
7 4 2 2 3 5 6 9 10 11 4 5 6 11 7 2 2 10 7
Yes No Yes Yes