#PU1160. USACO 2021 December Contest, Silver — Problem 3. Convoluted Intervals
USACO 2021 December Contest, Silver — Problem 3. Convoluted Intervals
USACO 2021 December Contest, Silver — Problem 3. Convoluted Intervals
题目描述
The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of intervals (), where the th interval starts at position on the number line and ends at position . Both and are integers in the range , where . To play the game, Bessie chooses some interval (say, the th interval) and her cousin Elsie chooses some interval (say, the th interval, possibly the same as Bessie's interval). Given some value , they win if . For every value of in the range , please count the number of ordered pairs for which Bessie and Elsie can win the game.
输入格式
The first line of input contains and . Each of the next lines describes an interval in terms of integers and .
输出格式
Please print lines as output, one for each value of in the range .
数据范围
Test cases 1-2 satisfy . Test cases 3-5 satisfy . Test cases 6-20 satisfy no additional constraints.
样例
样例 1
2 5
1 3
2 5
0
0
1
3
4
4
4
3
3
1
1
In this example, for just $k=3$, there are three ordered pairs that will allow
Bessie and Elie to win: $(1, 1)$, $(1, 2),$ and $(2, 1)$.
提示
may want to use 64-bit integers (e.g., "long long" ints in C or C++). Problem credits: Benjamin Qi