CF1297I.Falling Blocks
普及/提高-
通过率：0%
AC君温馨提醒
该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
The first line contains two integers n and d ( 1≤n,d≤105 ) — the number of falling blocks and the length of the flat surface.
The i -th of the following n lines contains integers li and ri ( 1≤li≤ri≤d ) — the coordinates of the i -th block.
输入格式
Output n integers. The i -th integer should be the number of blocks that will be left after the i -th block falls.
输出格式
The first example is explained above.
In the second example, this is what happens after each block falls:
- Block 1 will stick to the flat surface.
- Block 2 will stick to the flat surface.
- Block 3 will stick to blocks 1 and 2 . Note that block 3 will not vaporize block 2 because it does not cover block 1 and is in contact with it.
- Block 4 will vaporize all the blocks and stick to the flat surface.
- Block 5 will stick to block 4
- Block 6 will stick to block 5 .
- Block 7 will stick to block 6 . Note that no blocks are vaporized because although block 7 covers block 4 and block 5 , they never come in contact.
- Block 8 vaporizes block 7 and sticks to block 6 .
输入输出样例
输入#1
3 3 1 2 2 3 1 3
输出#1
1 2 1
输入#2
8 6 1 2 3 3 2 3 1 3 2 4 3 6 1 5 1 5
输出#2
1 2 3 1 2 3 4 4
说明/提示
The first example is explained above.
In the second example, this is what happens after each block falls:
- Block 1 will stick to the flat surface.
- Block 2 will stick to the flat surface.
- Block 3 will stick to blocks 1 and 2 . Note that block 3 will not vaporize block 2 because it does not cover block 1 and is in contact with it.
- Block 4 will vaporize all the blocks and stick to the flat surface.
- Block 5 will stick to block 4
- Block 6 will stick to block 5 .
- Block 7 will stick to block 6 . Note that no blocks are vaporized because although block 7 covers block 4 and block 5 , they never come in contact.
- Block 8 vaporizes block 7 and sticks to block 6 .