A2436 | TET-Tetris 3D
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
最近，有人发明了一种三维版的俄罗斯方块。和二维版本类似，一些立方体按照一定的顺序掉落，直到碰到别的方块或是地面才会停止掉落。立方体停止掉落后会一直保持掉落时的位置，直到游戏结束。
你的朋友决定以这个新版本的俄罗斯方块为背景，出一道题。给出每个立方体的掉落顺序和其掉落的轨迹，在所有方块完成掉落后求出最高方块的高度。在这个游戏中，方块均垂直下落，且方块不会旋转或翻转。为了方便描述，我们会建立一个空间直角坐标系，该坐标系的原点为地面的一角，并且坐标轴与地面边缘平行。
现在轮到你解决这个问题了。
你的朋友决定以这个新版本的俄罗斯方块为背景，出一道题。给出每个立方体的掉落顺序和其掉落的轨迹，在所有方块完成掉落后求出最高方块的高度。在这个游戏中，方块均垂直下落，且方块不会旋转或翻转。为了方便描述，我们会建立一个空间直角坐标系，该坐标系的原点为地面的一角，并且坐标轴与地面边缘平行。
现在轮到你解决这个问题了。
输入格式
### 输入格式
第一行三个整数 $D,S,N$，分别为地面的长度，宽度，和将要掉落的立方体数量。
接下来 $N$ 行，每行五个整数 $d_i,s_i,w_i,x_i,y_i$，描述一个掉落的立方体。其中 $d_i,s_i,w_i$ 分别代表立方体的长，宽，高。立方体的底面（即长 $\times$ 宽的那一面）将正对地面。立方体底面四个角在地面的投影坐标分别为 $(x_i,y_i)$，$(x_i+d_i,y_i)$，$(x_i,y_i+s_i)$，$(x_i+d_i,y_i+s_i)$。
第一行三个整数 $D,S,N$，分别为地面的长度，宽度，和将要掉落的立方体数量。
接下来 $N$ 行，每行五个整数 $d_i,s_i,w_i,x_i,y_i$，描述一个掉落的立方体。其中 $d_i,s_i,w_i$ 分别代表立方体的长，宽，高。立方体的底面（即长 $\times$ 宽的那一面）将正对地面。立方体底面四个角在地面的投影坐标分别为 $(x_i,y_i)$，$(x_i+d_i,y_i)$，$(x_i,y_i+s_i)$，$(x_i+d_i,y_i+s_i)$。
输出格式
### 输出格式
输出一个整数，即方块掉落结束后最高方块的高度。
输出一个整数，即方块掉落结束后最高方块的高度。
输入输出样例
输入 #1
7 5 4 4 3 2 0 0 3 3 1 3 0 7 1 2 0 3 2 3 3 2 2
输出 #1
6
### 数据范围
$1 \leq N \leq 20\,000$，$1 \leq D,S \leq 1\,000$，$d_i,s_i \geq 1$，$1 \leq w_i \leq 100\,000$，$0 \leq x_i,d_i+x_i \leq D$，$0 \leq y_i,s_i+y_i \leq S$。
$1 \leq N \leq 20\,000$，$1 \leq D,S \leq 1\,000$，$d_i,s_i \geq 1$，$1 \leq w_i \leq 100\,000$，$0 \leq x_i,d_i+x_i \leq D$，$0 \leq y_i,s_i+y_i \leq S$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？