P9426 [Lanqiao Cup 2023 National B] Claw Machine

Xiaoming took $n$ line segments to practice playing a claw machine. He laid all the segments on the number line. For the $i$-th segment, its left endpoint is at $l_i$ and its right endpoint is at $r_i$. Xiaoming uses $m$ intervals to “frame” these segments. The range of the $i$-th interval is $[L_i, R_i]$. If at least half of a segment’s length is contained in some interval, then the segment is considered to be framed by that interval. Please compute how many segments are framed by each interval.

The input has a total of $n + m + 1$ lines. The first line contains two positive integers $n, m$. The next $n$ lines each contain two integers $l_i, r_i$. The next $m$ lines each contain two integers $L_i, R_i$.

Output a total of $m$ lines, each containing one integer.

### Test Case Scale and Conventions - For $20\%$ of the testdata, $n, m \le 10^3$ is guaranteed. - For $100\%$ of the testdata, $n, m \le 10^5$ is guaranteed, $l_i < r_i$, $0 < l_i, r_i, L_i, R_i \le 10^6$, and $\max \{r_i − l_i\} \le \min \{R_i − L_i\}$. Problem H of Group B (C/C++), College Division, Finals of the 14th Lanqiao Cup Software Contest. Translated by ChatGPT 5