P12151 【MX-X11-T5】Tetris

原题链接：。 --- 「興味がないこと本気じゃないもの全部後回しで」 「知ってることは知らんぷり 私は終わってる」 「恥ずかしい過去知ってるやつらの記憶消させて」 「迷惑かけてごめんってば ねえ誰か助けて」

Given an integer sequence $h_i$ of length $n$, along with $n$ pairs $(a_i, b_i)$ and a positive integer $k$. For each position $p$, you can perform one of the following operations: - **Activate position $p$**: Choose a position $j$ satisfying $1 \le j - p \le k$, then update $h_p \leftarrow h_p + a_p$ and $h_j \leftarrow h_j - b_p$. **Each position can be activated at most once**. - **Do not activate position $p$**. There are $q$ queries $(l_i, r_i, x_i)$. For each query, under the constraints that only positions $p \in [l_i, r_i]$ can be activated and the corresponding $j$ must lie within $[p+1, \min(p+k, r_i)]$, determine whether there exists a way to activate positions such that $\max_{t=l_i}^{r_i} h_t \le x_i$. Queries are independent: the sequence $h$ is restored to its original state at the start of each query, and no activation choices are retained between queries.

**Multiple test cases.** The first line contains two integers $c$ and $T$, representing the subtask number and the number of test cases, respectively. Sample inputs satisfy $c=0$. For each test case: - The first line contains three integers $n, q, k$, representing the sequence length, number of queries, and activation range parameter. - The second line contains $n$ integers $h_1, h_2, \ldots, h_n$. - The third line contains $n$ integers $a_1, a_2, \ldots, a_n$. - The fourth line contains $n$ integers $b_1, b_2, \ldots, b_n$. - The next $q$ lines each contain three integers $l_i, r_i, x_i$, describing the $i$-th query.

For each query, output `Yes` or `No` indicating whether a valid activation scheme exists.

## Explanation #1 **Sample 1 Explanation:** For the query $(2, 3, 1)$, activating position $2$ updates $h_2$ to $0 + a_2 = 1$ and $h_3$ to $2 - b_2 = 2 - 8 = -6$. The maximum value in $[2, 3]$ is $1$, satisfying the condition. For the query $(1, 3, 1)$, no valid activation exists. ## Constraints **This problem uses subtask scoring.** For all test data: $1 \le T \le 3$, $1 \le n \le 2 \times 10^4$, $1 \le q \le 10^5$, $0 \le h_i, a_i, b_i, x_i \le 10^6$, $1 \le l_i \le r_i \le n$, $1 \le k \le 5$. | Subtask | $n \le$ | $q \le$ | $k \le$ | $T \le$ | Special Property | Points | Time Limit | |:---------:|:------------:|:-----------:|:---------:|:---------:|:-------------------:|:--------:|:------------:| | 1 | 10 | 10 | 5 | 3 | None | 5 | 1 s | | 2 | 1000 | 1000 | 5 | 1 | None | 10 | 1 s | | 3 | $2 \times 10^4$ | $10^5$ | 5 | 3 | A | 10 | 4 s | | 4 | $10^4$ | $10^4$ | 3 | 1 | B | 5 | 1 s | | 5 | $10^4$ | $10^4$ | 3 | 1 | None | 10 | 1 s | | 6 | $2 \times 10^4$ | $2 \times 10^4$ | 4 | 1 | B | 5 | 1 s | | 7 | $2 \times 10^4$ | $2 \times 10^4$ | 4 | 1 | None | 10 | 1 s | | 8 | $2 \times 10^4$ | $4 \times 10^4$ | 4 | 2 | B | 5 | 1 s | | 9 | $2 \times 10^4$ | $4 \times 10^4$ | 4 | 2 | None | 10 | 1 s | | 10 | $2 \times 10^4$ | $10^5$ | 5 | 3 | None | 30 | 4 s | - **Special Property A**: For all queries, $l_i = 1$ and $r_i = n$. - **Special Property B**: For all queries, $x_i = x_j$ for any $i, j$. **Note:** Be mindful of the problem's time limits. Translated by DeepSeek R1