A13203. Falling Blocks
编程题
普及/提高-
知识点
题目描述
The first line contains two integers $n$ and $d$ ( $1 \le n, d \le 10^5$ ) — the number of falling blocks and the length of the flat surface.
The $i$ -th of the following $n$ lines contains integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le d$ ) — the coordinates of the $i$ -th block.
The $i$ -th of the following $n$ lines contains integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le 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$ .
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$ .
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$ .