「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
一个整数表示所有立方体落下后最高的方块的高度.
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
题解
二维线段树。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int D,S,N; int ql,qr,qd,qu; struct segx{ int v[3005],tag[3005]; void change(int k,int l,int r,int x,int y,int val){ v[k]=max(v[k],val); if(l==x&&y==r){tag[k]=max(tag[k],val);return;} int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,min(mid,y),val); if(y>mid)change(k<<1|1,mid+1,r,max(x,mid+1),y,val); } int query(int k,int l,int r,int x,int y){ if(l==x&&y==r)return v[k]; int mid=(l+r)>>1,ans=tag[k]; if(x<=mid)ans=max(ans,query(k<<1,l,mid,x,min(mid,y))); if(y>mid)ans=max(ans,query(k<<1|1,mid+1,r,max(x,mid+1),y)); return ans; } }; struct segy{ segx v[3005],tag[3005]; void change(int k,int l,int r,int x,int y,int val){ v[k].change(1,1,S,qd,qu,val); if(l==x&&y==r){tag[k].change(1,1,S,qd,qu,val);return;} int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,min(mid,y),val); if(y>mid)change(k<<1|1,mid+1,r,max(x,mid+1),y,val); } int query(int k,int l,int r,int x,int y){ if(l==x&&y==r)return v[k].query(1,1,S,qd,qu); int mid=(l+r)>>1,ans=tag[k].query(1,1,S,qd,qu);; if(x<=mid)ans=max(ans,query(k<<1,l,mid,x,min(mid,y))); if(y>mid)ans=max(ans,query(k<<1|1,mid+1,r,max(x,mid+1),y)); return ans; } }T; int main() { D=read();S=read();N=read(); int d,s,w,x,y; for(int i=1;i<=N;i++) { d=read();s=read();w=read();x=read();y=read(); ql=x+1;qr=x+d;qd=y+1;qu=y+s; int ans=T.query(1,1,D,ql,qr); T.change(1,1,D,ql,qr,ans+w); } qd=1;qu=S; printf("%d\n",T.query(1,1,D,1,D)); return 0; } |
计数器 9787728
OI 课件=>
OI 课件=>
黄学长的代码真的很有灵性啊…… /05
黄学长的代码真的很有灵性啊……