Задача №115227. Яблоки по корзинам
У Саши есть \(n\) яблок с целыми весами \(w_1, w_2, \ldots, w_n\), которые лежат на столе, а также две вместительные корзины.
Саша выбирает целое число \(k\) и рассматривает яблоки с весом не больше \(k\). После этого она может положить каждое яблоко с весом \(w_i \le k\) в одну из двух корзин, либо оставить его на столе. Яблоки с весом \(w_i > k\) в любом случае остаются на столе.
Назовем пару чисел \((x, y)\) \(k\)-достижимой , если Саша может положить некоторые яблоки с весом не больше \(k\) в корзины так, чтобы сумма весов яблок в первой корзине оказалась равна \(x\), а сумма весов яблок во второй корзине оказалась равна \(y\). Назовем пару чисел \((a, b)\) \(k\)-идеальной , если для всех \(x\) и \(y\), где \(0 \le x \le a\) и \(0 \le y \le b\), пара \((x, y)\) является \(k\)-достижимой.
Саша рассматривает \(q\) троек чисел \(k\), \(a\), \(b\) и для каждой из них хочет понять, является ли \(k\)-идеальной пара \((a, b)\).
В первой строке даны два целых числа \(n\) и \(q\) — количество яблок, которые есть у Саши, и количество запросов, которые вам надо обработать (\(1 \le n, q \le 300\,000\)).
Во второй строке даны \(n\) целых чисел \(w_1\), \(w_2\), ..., \(w_n\) — веса яблок, которые есть у Саши (\(1 \le w_i \le 10^{12}\)).
В третьей строке находится целое число \(z\), которое используется для формирования запросов, на которые необходимо ответить (\(0 \le z \le 10^6\)).
В следующих \(q\) строках даны описания запросов. Запросы пронумерованы от \(1\) до \(q\). Каждая строка содержит три целых числа \(j\), \(c\) и \(d\) (\(0 \le j, c, d \le 10^{18}\)). Запрос формируется из чисел в этой строке по следующим правилам. Вычислим \(v\), как сумму номеров запросов, сделанных до текущего, для которых заданная в запросе пара \((a, b)\) оказалась \(k\)-идеальной. Тогда в текущем запросе \(k = j - v\cdot z\); \(a = c - v \cdot z\); \(b = d - v \cdot z\). Гарантируется, что \(k, a, b \geq 0\).
Обратите внимание, что при \(z = 0\) (что верно для большинства подзадач), значения \(k\), \(a\) и \(b\) равны \(j\), \(c\) и \(d\) соответственно. То есть параметры запроса не зависят от ответов на предыдущие запросы и даны во входных данных в явном виде.
На каждый запрос выведите « Yes », если пара \((a, b)\) в данном запросе является \(k\)-идеальной, иначе выведите « No ».
| Дополнительные ограничения | ||||||
| Подз. | Баллы | \(n\), \(q\) | \(a, b\) | \(k\) | \(z\) | Необх. подзадачи |
| 1 | 9 | \(n, q \le 10\) | \(z=0\) | |||
| 2 | 6 | \(n \le 100\) | \(a \le 100\,000\), \(b = 0\) | \(k = 10^{18}\) | \(z=0\) | |
| 3 | 3 | \(b = 0\) | \(k = 10^{18}\) | \(z=0\) | 2 | |
| 4 | 6 | \(n, q \le 100\) | \(a, b \le 300\) | \(k = 10^{18}\) | \(z=0\) | |
| 5 | 6 | \(n \le 100\) | \(a, b \le 300\) | \(k = 10^{18}\) | \(z=0\) | 4 |
| 6 | 2 | \(n \le 1\,500\) | \(a, b \le 1\,500\) | \(k = 10^{18}\) | \(z=0\) | 4–5 |
| 7 | 6 | \(n \le 5\,000\) | \(a, b \le 5\,000\) | \(k = 10^{18}\) | \(z=0\) | 4–6 |
| 8 | 2 | \(a, b \le 200\,000\) | \(k = 10^{18}\) | \(z=0\) | 2, 4–7 | |
| 9 | 9 | \(k = 10^{18}\) | \(z=0\) | 2–8 | ||
| 10 | 3 | \(b = 0\) | \(z=0\) | 2–3 | ||
| 11 | 6 | \(n, q \le 100\) | \(a, b \le 300\) | \(z=0\) | 4 | |
| 12 | 6 | \(n \le 100\) | \(a, b \le 300\) | \(z=0\) | 4–5, 11 | |
| 14 | 2 | \(n \le 1\,500\) | \(a, b \le 1\,500\) | \(z=0\) | 4–6, 11-13 | |
| 15 | 6 | \(n \le 5\,000\) | \(a, b \le 5\,000\) | \(z=0\) | 4–7, 11-14 | |
| 16 | 2 | \(a, b \le 200\,000\) | \(z=0\) | 4–8, 11–15 | ||
| 17 | 6 | \(z=0\) | 1–16 | |||
| 18 | 18 | У, 1–17 | ||||
8 5 17 1 3 2 100 5 6 1 0 6 15 3 9 4 4 5 15 3 17 34 1 16 33 2
Yes No No Yes No
8 5 17 1 3 2 100 5 6 1 1 6 15 3 10 5 5 6 16 4 18 35 2 21 38 7
Yes No No Yes No