P7992 [USACO21DEC] Convoluted Intervals S

The cows are trying hard to invent fun new games to play. One of their current projects involves a set of $N$ intervals ($1 \le N \le 2 \cdot 10^5$), where the $i$-th interval starts at position $a_i$ on the number line and ends at position $b_i \ge a_i$. Both $a_i$ and $b_i$ are integers in the range $0 \ldots M$, where $1 \le M \le 5000$. The game is played as follows: Bessie chooses an interval (suppose it is the $i$-th interval), and her cousin Elsie chooses an interval (suppose it is the $j$-th interval, which may be the same as Bessie's). Given a value $k$, they win if $a_i + a_j \le k \le b_i + b_j$. For each value $k$ in the range $0 \ldots 2M$, compute the number of ordered pairs $(i, j)$ such that Bessie and Elsie can win the game.

The first line of input contains $N$ and $M$. The next $N$ lines each describe an interval as integers $a_i$ and $b_i$.

Output $2M+1$ lines. In order, each line should contain the answer for each $k$ in the range $0 \ldots 2M$.

[Sample Explanation] In this example, for $k = 3$, there are three ordered pairs that allow Bessie and Elsie to win: $(1, 1)$, $(1, 2)$, and $(2, 1)$. [Constraints] - Test cases 1-2 satisfy $N \le 100, M \le 100$. - Test cases 3-5 satisfy $N \le 5000$. - Test cases 6-20 have no additional constraints. Translated by ChatGPT 5