28502번 - Яблоки по корзинам 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 70 | 2 | 2 | 14.286% |
문제
У Саши есть $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$, $\dots$, $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>>.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 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$ |
| 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$ |
| 6 | 2 | $n \le 1\,500$, $a, b \le 1\,500$, $k = 10^{18}$, $z=0$ |
| 7 | 6 | $n \le 5\,000$, $a, b \le 5\,000$, $k = 10^{18}$, $z=0$ |
| 8 | 2 | $a, b \le 200\,000$, $k = 10^{18}$, $z=0$ |
| 9 | 9 | $k = 10^{18}$, $z=0$ |
| 10 | 3 | $b = 0$, $z=0$ |
| 11 | 6 | $n, q \le 100$, $a, b \le 300$, $z=0$ |
| 12 | 6 | $n \le 100$, $a, b \le 300$, $z=0$ |
| 13 | 2 | $n, q \le 1\,500$, $a, b \le 1\,500$, $z=0$ |
| 14 | 2 | $n \le 1\,500$, $a, b \le 1\,500$, $z=0$ |
| 15 | 6 | $n \le 5\,000$, $a, b \le 5\,000$, $z=0$ |
| 16 | 2 | $a, b \le 200\,000$, $z=0$ |
| 17 | 6 | $z=0$ |
| 18 | 18 |
예제 입력 1
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
예제 출력 1
Yes No No Yes No
예제 입력 2
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
예제 출력 2
Yes No No Yes No
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.