← 返回题目列表

AtCoder · typical90_ac

029. 长砖(★5)

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

配点: 5 点

問題文

W 方形单元格左右排列。最初,对于所有零件,高度为 0 。这里的高度 1 长方形砖 按顺序堆叠 N 块。高度 粘在 h 表面的砖顶部的高度为 h+1 。

i 下一块要砌的砖是从左边开始的。 放置它,使其刚好覆盖第 L_i 个加油站开始 R_i 个方格。此时,将胶粘在砖块将覆盖的最高水平表面上。

求每块砖顶部的高度。

制約

  • 2 \leq W \leq 5 \times 10^5
  • 1 \leq N \leq 2.5 \times 10^5
  • 1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
  • 输入全部为整数

小作业/分数

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您已正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (1 点): W \leq 9000,\ N \leq 9000
  2. (1 点): N \leq 9000
  3. (3分):没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

W N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

i (1 \leq i \leq N) 行中, i 请以整数形式输出要堆叠的砖块顶部的高度。


入力例 1

100 4
27 100
8 39
83 97
24 75

出力例 1

1
2
2
3

i 砖 它被称为 i 。
砖 1 粘在物体的表面上,因此顶面的高度为 1 。
砖 2 是一块砖 1 由于它是粘在顶面上的,所以顶面的高度是 2 。
砖 3 是一块砖 1 由于它是粘在顶面上的,所以顶面的高度是 2 。
砖 4 是一块砖 2 由于它是粘在顶面上的,所以顶面的高度是 3 。


入力例 2

3 5
1 2
2 2
2 3
3 3
1 2

出力例 2

1
2
3
4
4

i 砖 它被称为 i 。
砖 1 粘在物体的表面上,因此顶面的高度为 1 。
砖 2 是一块砖 1 由于它是粘在顶面上的,所以顶面的高度是 2 。
砖 3 是一块砖 2 由于它是粘在顶面上的,所以顶面的高度是 3 。
砖 4 是一块砖 3 由于它是粘在顶面上的,所以顶面的高度是 4 。
砖 5 是一块砖 3 由于它是粘在顶面上的,所以顶面的高度是 4 。


入力例 3

10 10
1 3
3 5
5 7
7 9
2 4
4 6
6 8
3 5
5 7
4 6

出力例 3

1
2
3
4
3
4
5
5
6
7

入力例 4

500000 7
1 500000
500000 500000
1 500000
1 1
1 500000
500000 500000
1 500000

出力例 4

1
2
3
4
5
6
7

*此输入示例是一个小作业 仅满足 2,3 约束。