#P6396. 万宁俄罗斯方块(大招版)
万宁俄罗斯方块(大招版)
题目描述
地面是无限长的水平直线。依次将 个矩形沿竖直方向从上方落下。第 个矩形的左右边界分别固定在 和 ,高度为 。矩形落到不能再下移时固定。矩形内部不能重叠,边界接触是允许的。
在地面上方,未被矩形覆盖的区域按四连通划分。被地面或矩形封闭、面积大于零的连通区域称为一个洞。求每个矩形落下并固定后新形成的洞数。
输入格式
第一行一个整数 。接下来 行,每行三个整数 ,依次给出矩形的左右边界和高度。
输出格式
输出 行。第 行给出第 个矩形落下并固定后新形成的洞数。
样例
8
1 2 3
1 4 1
4 6 3
1 2 1
7 8 4
1 3 1
3 7 1
8 9 5
0
0
1
0
0
0
2
0
第 3 个矩形落下后形成 1 个洞,第 7 个矩形落下后形成 2 个洞。原 PDF 的第 2 页给出了堆叠示意图。
数据范围
对全部数据,,,。
| 子任务 | 的上界 | 分数 |
|---|---|---|
| 1 | 3 | |
| 2 | 17 | |
| 3 | 30 | |
| 4 | ||
| 5 | 20 |
题目为「HNOI 2009」积木游戏的加强版。原题面及样例图 PDF