← 返回题目列表

Codeforces · 1965/F

F. 会议

中文机器翻译题面 查看原题

您被要求组织一次非常重要的艺术会议。第一步是选择日期。

会议必须持续一定的连续天数。每天必须有一位讲师表演,同一位讲师不能表演多次。

您询问 $$$n$$$ 潜在讲师是否可以参加会议。讲师$$$i$$$表示他们可以在$$$l_i$$$到$$$r_i$$$期间的任何一天进行表演。

如果有一种方法可以将某一天的某一天指定为会议日期,则可以为该天的每一天分配一位可用的讲师,为每位讲师分配不超过一天。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,找出有多少种方法来选择 $$$k$$$ 连续天的一段作为会议日期。

输入

输入的第一行包含一个整数 $$$n$$$ — 潜在讲师的数量 ($$$1 \le n \le 2 \cdot 10^5$$$)。

接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ - 第 $$$i$$$ 位讲师的可用天数 ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$)。

输出

打印 $$$n$$$ 整数,其中第 $$$k$$$ 个数字表示选择 $$$k$$$ 连续天的时间段作为会议日期的方式数。

示例

输入 #1

3
1 2
3 4
5 6

输出 #1

6
2
0

输入 #2

5
1 3
1 3
1 3
1 3
1 3

输出 #2

3
2
1
0
0

注意

在第一个测试用例中,可以在 $$$1$$$ 到 $$$6$$$ 之间的任何一天组织为期一天的会议。为期两天的会议可以从$$$2$$$天到$$$3$$$天,以及从$$$4$$$天到$$$5$$$天组织。

在第二个测试用例中,五名讲师只能从$$$1$$$天到$$$3$$$天进行表演,因此不可能组织超过三天的会议。