P15555 [CCPC 2025 Harbin Site] Contest

The Cook Chicken Potato Contest is one of the most famous competitions in the chef world. The venue always provides $k$ stoves, and the organizer Little $Q$ will divide the contestants into $k$ teams with **the same number of people**. To test teamwork among contestants and make the contest more exciting, Little $Q$ will arrange the teams so that the skill gaps among contestants in the same team are **as large as possible**. Suppose the contestants' skills are $a_1,a_2,\ldots,a_n$, and the teams they belong to are $t_1,t_2,\ldots,t_n$. Little $Q$ defines the excitement of the contest as: $$ D=\mathop{\min}_{1 \le i < j \le n} \begin{cases} |a_i - a_j| & t_i = t_j \\ +\infty & t_i \neq t_j \end{cases} $$ Now, $n$ possible contestants are given in nondecreasing order of skill. Since a contestant's skill is not fixed, the $i$-th contestant is described by an interval $[l_i,r_i]$, meaning their actual skill in a contest can be **any real number** in this interval. Also, because the contestants' skills are monotonic nondecreasing by index, it is guaranteed that for all $\forall 1 \le i < j \le n$, we have $l_i \leq l_j, r_i \leq r_j$. Little $Q$ has $q$ contest plans. In the $i$-th plan, contestants with indices between $L_i$ and $R_i$ will be invited. You need to help Little $Q$ determine whether there exists a way to assign teams such that the contest excitement **may** be at least $D_i$.

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. Then the test cases follow. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^5$, $1 \le k \le \min(5, n)$), representing the number of possible contestants and the number of teams. The next $n$ lines each contain two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^{12}$), describing the possible skill range of the $i$-th contestant. It is guaranteed that for all $\forall 1 \le i < n$, $l_i \le l_{i+1}$ and $r_i \le r_{i+1}$. The next line contains an integer $q$ ($1 \le q \le 10^5$), indicating the number of contest plans. The next $q$ lines each contain three integers $L_i$, $R_i$, and $D_i$ ($1 \le L_i \le R_i \le n$, $k \mid (R_i - L_i + 1)$, $0 \le D_i \le 10^{12}$), meaning that in the $i$-th plan, contestants with indices from $L_i$ to $R_i$ will be invited, and Little $Q$ expects the excitement to be $D_i$. It is guaranteed that $\sum n$ over all test cases does not exceed $10^6$, and $\sum q$ does not exceed $10^5$.

For each test case, output $q$ lines. For the $i$-th line, output `YES` or `NO`, indicating whether Little $Q$'s expected value for the $i$-th plan may be achievable. You may output the answer in any letter case (uppercase or lowercase). For example, `yEs`, `yes`, `Yes`, and `YES` are all considered affirmative answers.

Translated by ChatGPT 5