1513: [POI2006]Tet-Tetris 3D
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 693 Solved: 227
[Submit][Status][Discuss]
Description
Task: Tetris 3D "Tetris" 游戏的作者决定做一个新的游戏, 一个三维的版本, 在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.
Input
第一行给出三个整数 D, S and N ( 1<= N<= 20 000, 1<= D, S <=1 000), 分别表示平板的长和宽以及下落立方体的数目. 接下来N 行每行描述一个立方体. 每行包含5个整数: d, s, w, x and y (1<= d, 0 <=x, d + x<= D, 1 <=s, 0<= y, s + y<= S, 1<= w <=100 000), 分别表示立方体的长\宽\高以及落下的左下角坐标, 长和宽都是平行于平板坐标轴的,落下后立方体着地的四个角坐标分别为: (x, y), (x + d, y), (x, y + s) and (x + d, y + s).
Output
一个整数表示所有立方体落下后最高的方块的高度.
Sample Input
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
Sample Output
6
HINT
Source
二维线段树。。因为不能下传标记。。所以要标记永久化。。一些细节花了我一下午时间调。。果真还是太弱了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int x,y,d,s,D,S,n,qu,qd,ql,qr,w;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
struct segx{
int v[3010],tag[3010];
void Update(int pos,int l,int r,int x,int y,int val){
v[pos] = max(val,v[pos]);
if (l==x && r==y) {tag[pos] = max(tag[pos],val);return;}
int mid = (l+r)>>1;
if (y<=mid) Update(pos<<1,l,mid,x,y,val);
else if (x>mid) Update(pos<<1|1,mid+1,r,x,y,val);
else Update(pos<<1,l,mid,x,mid,val),Update(pos<<1|1,mid+1,r,mid+1,y,val);
}
int Query(int pos,int l,int r,int x,int y){
if (l==x && r==y) return v[pos];
int mid = (l+r)>>1,res = tag[pos];
if (y<=mid) res = max(res,Query(pos<<1,l,mid,x,y));
else if (x>mid) res = max(res,Query(pos<<1|1,mid+1,r,x,y));
else res = max(res,max(Query(pos<<1,l,mid,x,mid),Query(pos<<1|1,mid+1,r,mid+1,y)));
return res;
}
};
struct segy{
segx v[3010],tag[3010];
void Update(int pos,int l,int r,int x,int y,int val){
v[pos].Update(1,1,S,qu,qd,val);
if (l==x && r==y) {tag[pos].Update(1,1,S,qu,qd,val);return;}
int mid = (l+r)>>1;
if (y<=mid) Update(pos<<1,l,mid,x,y,val);
else if (x>mid) Update(pos<<1|1,mid+1,r,x,y,val);
else Update(pos<<1,l,mid,x,mid,val),Update(pos<<1|1,mid+1,r,mid+1,y,val);
}
int Query(int pos,int l,int r,int x,int y){
if (l==x && r==y) return v[pos].Query(1,1,S,qu,qd);
int mid = (l+r)>>1,res = tag[pos].Query(1,1,S,qu,qd);
if (y<=mid) res = max(res,Query(pos<<1,l,mid,x,y));
else if (x>mid) res = max(res,Query(pos<<1|1,mid+1,r,x,y));
else res = max(res,max(Query(pos<<1,l,mid,x,mid),Query(pos<<1|1,mid+1,r,mid+1,y)));
return res;
}
} T;
int main(){
D = read();S = read();n = read();
for (int i=1;i<=n;i++){
d = read();s = read();w = read();x = read();y = read();
ql = x+1;qr = x+d;qu = y+1;qd = y+s;
int ans = T.Query(1,1,D,ql,qr);
T.Update(1,1,D,ql,qr,ans+w);
}
ql = 1;qr = D;qu = 1;qd = S;
printf("%d",T.Query(1,1,D,1,D));
}
/*
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
*/
评论 (0)
