配点: 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 点): W \leq 9000,\ N \leq 9000
- (1 点): N \leq 9000
- (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 约束。