首页 > 代码库 > bzoj1513: [POI2006]Tet-Tetris 3D
bzoj1513: [POI2006]Tet-Tetris 3D
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
一个整数表示所有立方体落下后最高的方块的高度.
zkw线段树套zkw线段树+标记永久化 维护区间最值
#include<cstdio>int n,D,S;int x1,y1,x2,y2,h,ans,a0=0;int tr[2][2111][2111][2];char buf[2000000],*ptr=buf-1;int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x;}inline void maxs(int&a,int b){if(a<b)a=b;}void g(int(*a)[2]){ int l=1023+y1,r=1025+y2,ld=0,rd=0; for(;l^r^1;l>>=1,r>>=1){ if(ld)maxs(ans,a[l][1]); if(rd)maxs(ans,a[r][1]); if(~l&1)ld=1,maxs(ans,a[l^1][0]); if(r&1)rd=1,maxs(ans,a[r^1][0]); } if(ld)maxs(ans,a[l][1]); if(rd)maxs(ans,a[r][1]); for(l>>=1;l;l>>=1)maxs(ans,a[l][1]);}void s(int(*a)[2]){ int l=1023+y1,r=1025+y2,ld=0,rd=0; for(;l^r^1;l>>=1,r>>=1){ if(ld)maxs(a[l][0],ans); if(rd)maxs(a[r][0],ans); if(~l&1)ld=1,maxs(a[l^1][0],ans),maxs(a[l^1][1],ans); if(r&1)rd=1,maxs(a[r^1][0],ans),maxs(a[r^1][1],ans); } if(ld)maxs(a[l][0],ans); if(rd)maxs(a[r][0],ans); for(l>>=1;l;l>>=1)maxs(a[l][0],ans);}void cal(){ ans=0; int l=1023+x1,r=1025+x2,ld=0,rd=0; for(;l^r^1;l>>=1,r>>=1){ if(ld)g(tr[1][l]); if(rd)g(tr[1][r]); if(~l&1)ld=1,g(tr[0][l^1]); if(r&1)rd=1,g(tr[0][r^1]); } if(ld)g(tr[1][l]); if(rd)g(tr[1][r]); for(l>>=1;l;l>>=1)g(tr[1][l]); ans+=h; maxs(a0,ans); l=1023+x1,r=1025+x2,ld=0,rd=0; for(;l^r^1;l>>=1,r>>=1){ if(ld)s(tr[0][l]); if(rd)s(tr[0][r]); if(~l&1)ld=1,s(tr[0][l^1]),s(tr[1][l^1]); if(r&1)rd=1,s(tr[0][r^1]),s(tr[1][r^1]); } if(ld)s(tr[0][l]); if(rd)s(tr[0][r]); for(l>>=1;l;l>>=1)s(tr[0][l]);}int main(){ fread(buf,1,sizeof(buf),stdin); D=_();S=_();n=_(); for(int i=0;i<n;++i){ x2=_();y2=_();h=_(); x1=_();y1=_(); x2+=x1;y2+=y1; ++x1;++y1; cal(); } printf("%d",a0); return 0;}
bzoj1513: [POI2006]Tet-Tetris 3D
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。