首页 > 代码库 > AC日记——楼房 codevs 2995
AC日记——楼房 codevs 2995
2995 楼房
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
地平线(x轴)上有n个矩(lou)形(fang)，用三个整数h[i],l[i],r[i]来表示第i个矩形：矩形左下角为(l[i],0)，右上角为(r[i],h[i])。地平线高度为0。在轮廓线长度最小的前提下，从左到右输出轮廓线。
输入描述 Input Description
第一行一个整数n，表示矩形个数
以下n行，每行3个整数h[i],l[i],r[i]表示第i个矩形。
输出描述 Output Description
第一行一个整数m，表示节点个数
以下m行，每行一个坐标表示轮廓线上的节点。从左到右遍历轮廓线并顺序输出节点。第一个和最后一个节点的y坐标必然为0。
样例输入 Sample Input
【样例输入】
2
3 0 2
4 1 3
【样例输入2】
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
样例输出 Sample Output
【样例输出】
6
0 0
0 3
1 3
1 4
3 4
3 0
【样例输出2】
14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0
数据范围及提示 Data Size & Hint
对于30%的数据，n<=100
对于另外30%的数据，n<=100000,1<=h[i],l[i],r[i]<=1000
对于100%的数据，1<=n<=100000,1<=h[i]<=10^9,-10^9<=l[i]<r[i]<=10^9
思路：
离散化+线段树
有的神犇说扫描线+堆更快，但是我不会。。
写了一个晚上
难在离散化和把线段放置
线段放置要考虑蛮多的情况
比如
恰好公用一个端点，可是不重叠
完全重叠
等等等等
离散化，用map记录下来，然后用迭代器全部存起来（stl大法好）
然后，用离散化好的点的两点之间的间隙建立线段树
然后把线段排序，从小到大
然后愉快的裸flag线段树
然后，像建树一样，一次优化<nlogn的check
如果前面的间隙的dis不等于现在的间隙的dis就输出
轻松ac（不知道wa了多少次re多少次）
来，上代码：
View Code
#include <map>#include <cstdio>#include <iostream>#include <algorithm>using namespace std;struct node { long long int l,r,dis;};struct node edge[100001];inline void read_int(long long int &now_);class T_tree { public: int l,r,mid; long long int dis,flag; void mid_() { mid=(l+r)>>1; } void flag_() { flag=0; } void dis_() { dis=0; }};class T_tree tree[100001*4*2];long long int n,if_Z,num=0,before=0,before_=0;long long int point[100001*2],ans=0,ans_now[100001*4],ans_dis[100001*4];char Cget;bool if_fi=true;map<long long int,long long int>if_;inline void read_int(long long int &now_){ now_=0,if_Z=1,Cget=getchar(); while(Cget<‘0‘||Cget>‘9‘) { if(Cget==‘-‘) if_Z=-1; Cget=getchar(); } while(Cget<=‘9‘&&Cget>=‘0‘) { now_=now_*10+Cget-‘0‘; Cget=getchar(); } now_*=if_Z;}inline bool cmp(struct node some1,struct node some2){ return some1.dis<some2.dis;}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis_(); return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r);}inline void tree_down(int now){ if(tree[now].l==tree[now].r) return ; tree[now<<1].dis=tree[now].flag; tree[now<<1].flag=tree[now].flag; tree[now<<1|1].dis=tree[now].flag; tree[now<<1|1].flag=tree[now].flag; tree[now].flag_();}void tree_change(int now,int l,int r,long long int dis){ if(tree[now].l==l&&tree[now].r==r) { tree[now].dis=dis; tree[now].flag=dis; tree_down(now); return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,dis); else if(r<=tree[now].mid) tree_change(now<<1,l,r,dis); else { tree_change(now<<1,l,tree[now].mid,dis); tree_change(now<<1|1,tree[now].mid+1,r,dis); }}int times=0;void tree_check(int now){ if(tree[now].l==tree[now].r) { if(tree[now].dis!=before) { ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } return ; } if(tree[now].flag) tree_down(now); tree_check(now<<1),tree_check(now<<1|1);}int main(){ read_int(n); for(int i=1;i<=n;i++) { read_int(edge[i].dis),read_int(edge[i].l),read_int(edge[i].r); if_[edge[i].l]=edge[i].l,if_[edge[i].r]=edge[i].r; } for(map<long long int,long long int>::iterator it=if_.begin();it!=if_.end();it++) { point[++num]=it->first; it->second=num; } tree_build(1,1,num+1); sort(edge+1,edge+n+1,cmp); for(int i=1;i<=n;i++) { tree_change(1,if_[edge[i].l],if_[edge[i].r]-1,edge[i].dis); } tree_check(1); printf("%lld\n",ans); for(int i=1;i<=ans;i++) printf("%lld %lld\n",ans_now[i],ans_dis[i]); return 0;}
附失败代码（>.<）：
#include <map>#include <cstdio>#include <iostream>#include <algorithm>using namespace std;struct node { int l,r,dis;};struct node edge[100001];inline void read_int(int &now_);class T_tree { public: int l,r,mid,dis,flag; void mid_() { mid=(l+r)>>1; } void flag_() { flag=0; } void dis_() { //read_int(dis); dis=0; }};class T_tree tree[100001*4*2];class T_tree ok[100001*4*2];int n,if_Z,num=0,before=0,before_=0;int point[100001*2],ans=0,ans_now[100001*2+1000],ans_dis[100001*2+1000];char Cget;bool if_fi=true;map<int,int>if_;inline void read_int(int &now_){ now_=0,if_Z=1,Cget=getchar(); while(Cget<‘0‘||Cget>‘9‘) { if(Cget==‘-‘) if_Z=-1; Cget=getchar(); } while(Cget<=‘9‘&&Cget>=‘0‘) { now_=now_*10+Cget-‘0‘; Cget=getchar(); } now_*=if_Z;}inline bool cmp(struct node some1,struct node some2){ return some1.dis<some2.dis;}void ok_build(int now,int l,int r){ ok[now].l=l,ok[now].r=r; if(l==r) return ; ok[now].mid_(); ok_build(now<<1,l,ok[now].mid); ok_build(now<<1|1,ok[now].mid+1,r);}void ok_down(int now){ if(ok[now].l==ok[now].r) return ; ok[now<<1].dis=ok[now].flag; ok[now<<1].flag=ok[now].flag; ok[now<<1|1].dis=ok[now].flag; ok[now<<1|1].flag=ok[now].flag; ok[now].flag=0;}void ok_change(int now,int l,int r){ if(ok[now].dis) return ; if(ok[now].l==ok[now].r) { ok[now].dis=1; ok[now].flag=1; ok_down(now); return ; } if(ok[now].flag) ok_down(now); if(l>ok[now].mid) ok_change(now<<1|1,l,r); else if(r<=ok[now].mid) ok_change(now<<1,l,r); else { ok_change(now<<1,l,ok[now].mid); ok_change(now<<1|1,ok[now].mid+1,r); }}bool ok_ko(int now,int to){ if(ok[now].dis) return true; if(ok[now].l==ok[now].r&&ok[now].l==to) { return false; } if(ok[now].flag) ok_down(now); if(ok[now].l>to) return ok_ko(now<<1|1,to); else return ok_ko(now<<1,to);}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis_(); return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r);}inline void tree_down(int now){ if(tree[now].l==tree[now].r) return ; tree[now<<1].dis=tree[now].flag; tree[now<<1].flag=tree[now].flag; tree[now<<1|1].dis=tree[now].flag; tree[now<<1|1].flag=tree[now].flag; tree[now].flag_();}void tree_change(int now,int l,int r,int dis){ if(tree[now].l==l&&tree[now].r==r) { tree[now].dis=dis; tree[now].flag=dis; tree_down(now); return ; } if(tree[now].flag) tree_down(now); if(l>tree[now].mid) tree_change(now<<1|1,l,r,dis); else if(r<=tree[now].mid) tree_change(now<<1,l,r,dis); else { tree_change(now<<1,l,tree[now].mid,dis); tree_change(now<<1|1,tree[now].mid+1,r,dis); }}int times=0;void tree_check(int now){ if(tree[now].l==tree[now].r) { /*if(tree[now].dis!=before_) { times++; if(times==1) { printf("%d %d\n",point[tree[now].l],before); printf("%d %d\n",point[tree[now].l],tree[now].dis); } else { printf("%d %d\n",point[tree[now].l],tree[now].dis); } before_=tree[now].dis; }*/ //printf("(%d,%d)",point[tree[now].l],tree[now].dis); if(tree[now].l==num+1) { if(before!=0) { //printf("%d %d\n",point[num],before); //printf("%d %d\n",point[num],0); ans_now[++ans]=point[num]; ans_dis[ans]=before; ans_now[++ans]=point[num]; ans_dis[ans]=0; } } else { if(ok_ko(1,tree[now].l-1)) { if(tree[now].dis!=before) { //printf("%d %d\n%d %d\n",point[tree[now].l],before,point[tree[now].l],tree[now].dis); ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } } else { if(before!=0) { //printf("%d %d\n",point[tree[now].l-1],point[tree[now].l]); ans_now[++ans]=point[tree[now].l-1]; ans_dis[ans]=before; ans_now[++ans]=point[tree[now].l-1]; ans_dis[ans]=0; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=0; ans_now[++ans]=point[tree[now].l]; ans_dis[ans]=tree[now].dis; before=tree[now].dis; } } } //printf("(%d %d)\n",point[tree[now].l],tree[now].dis); return ; } if(tree[now].flag) tree_down(now); tree_check(now<<1),tree_check(now<<1|1);}int main(){ read_int(n); for(int i=1;i<=n;i++) { read_int(edge[i].dis),read_int(edge[i].l),read_int(edge[i].r); if_[edge[i].l]=edge[i].l,if_[edge[i].r]=edge[i].r; } // printf("\n\n"); for(map<int,int>::iterator it=if_.begin();it!=if_.end();it++) { point[++num]=it->first; it->second=num; // printf("%d %d\n",num,point[num]); } tree_build(1,1,num+1); ok_build(1,0,num-1); ok_change(1,0,0); sort(edge+1,edge+n+1,cmp); for(int i=1;i<=n;i++) { printf("%d %d\n",if_[edge[i].l],if_[edge[i].r]); } printf("\n\n"); for(int i=1;i<=n;i++) { //printf("%d %d %d\n\n",if_[edge[i].l],if_[edge[i].r],edge[i].dis); tree_change(1,if_[edge[i].l],if_[edge[i].r],edge[i].dis); ok_change(1,if_[edge[i].l],if_[edge[i].r]-1); printf("%d %d\n",if_[edge[i].l],if_[edge[i].r]-1); //ans=0; //before=0; //tree_check(1); //printf("\n"); //printf("%d %d %d\n",if_[edge[i].l],if_[edge[i].r],edge[i].dis); } printf("\n\n"); //ans=0; //before=0; tree_check(1); //printf("\n\n"); printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d %d\n",ans_now[i],ans_dis[i]); return 0;}
AC日记——楼房 codevs 2995
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。