P11110 [ROI 2023] Tao Tao Packs Apples (Day 2)

Translated from [ROI 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf).

Tao Tao has $n$ apples with integer weights $w_1,w_2,\dots,w_n$. They are placed on a table, and there are also two baskets with large enough capacity. Tao Tao chooses an integer $k$. For each apple with weight $w_i \le k$, he may put it into one of the baskets, or leave it on the table. Apples with weight greater than $k$ will always remain on the table. If Tao Tao can place the apples of weight at most $k$ into the baskets so that the total weight of apples in the first basket equals $x$, and the total weight of apples in the second basket equals $y$, then $(x, y)$ is called a reachable pair for $k$. If for all $x$ and $y$ satisfying $0 \le x \le a$ and $0 \le y \le b$, $(x, y)$ is a reachable pair for $k$, then $(a, b)$ is called $k$-perfect. Tao Tao will ask you $q$ times. For each triple $(k,a,b)$, determine whether $(a, b)$ is $k$-perfect.

The first line contains two integers $n$ and $q$, representing the number of apples Tao Tao has and the number of queries to process ($1 \le n, q \le 300,000$). The second line contains $n$ integers $w_1,w_2,\dots,w_n$, representing the weights of the apples ($1 \le w_i \le 10^{12}$). The third line contains an integer $z$, which will be used in the following input ($0 \le z \le 10^6$). The next $q$ lines describe the queries. Queries are numbered from $1$ to $q$. Each line contains three integers $j,c,d$ ($0 \le j, c, d \le 10^{18}$), meaning that in this query $k = j - v \times z,a = c - v \times z,b = d - v \times z$, where $v$ is the sum of the indices of the previous queries whose answers were `Yes`. It is guaranteed that $k,a,b \ge 0$. In this problem, for most testdata, $z$ equals $0$. In this case, the values of $k,a,b$ are $j,c,d$, respectively.

For each query, if the pair $(a, b)$ is $k$-perfect in that query, output `Yes`; otherwise output `No`.

 Translated by ChatGPT 5