首页 > 代码库 > BZOJ 1513: [POI2006]Tet-Tetris 3D
BZOJ 1513: [POI2006]Tet-Tetris 3D
Description
三维空间从上落下几个长方体,问最后的最高高度.
Solution
二维线段树.
感觉这种东西是可以yy出来的吧..
对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.
开4倍内存会MLE...
Code
/************************************************************** Problem: 1513 User: BeiYu Language: C++ Result: Accepted Time:14660 ms Memory:143344 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; #define mid ((l+r)>>1)#define lc (o<<1)#define rc (o<<1|1)const int M = 1005; inline int in(int x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } int D,S,N;int d,s,w,x,y;int ql,qr,qx,qy; struct Node { int d[M*3],g[M*3]; void Change(int o,int l,int r,int L,int R,int v) { d[o]=max(d[o],v); if(L<=l && r<=R) return void( g[o]=max(g[o],v) ); if(L<=mid) Change(lc,l,mid,L,R,v); if(R>mid) Change(rc,mid+1,r,L,R,v); } int Query(int o,int l,int r,int L,int R) { if(L<=l && r<=R) return d[o]; int res=g[o]; if(L<=mid) res=max(res,Query(lc,l,mid,L,R)); if(R>mid) res=max(res,Query(rc,mid+1,r,L,R)); return res; }}; struct Seg { Node d[M*3],g[M*3]; void Change(int o,int l,int r,int L,int R,int v) { d[o].Change(1,1,S,qx,qy,v); if(L<=l && r<=R) return void( g[o].Change(1,1,S,qx,qy,v) ); if(L<=mid) Change(lc,l,mid,L,R,v); if(R>mid) Change(rc,mid+1,r,L,R,v); } int Query(int o,int l,int r,int L,int R) { if(L<=l && r<=R) return d[o].Query(1,1,S,qx,qy); int res=g[o].Query(1,1,S,qx,qy); if(L<=mid) res=max(res,Query(lc,l,mid,L,R)); if(R>mid) res=max(res,Query(rc,mid+1,r,L,R)); return res; }}py;int main() { for(D=in(),S=in(),N=in();N--;) { d=in(),s=in(),w=in(),x=in(),y=in(); ql=x+1,qr=x+d,qx=y+1,qy=y+s; int tmp=py.Query(1,1,D,ql,qr); py.Change(1,1,D,ql,qr,tmp+w); } qx=1,qy=S; printf("%d\n",py.Query(1,1,D,1,D)); return 0;}
BZOJ 1513: [POI2006]Tet-Tetris 3D
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。