nolonger 1104K 249MS G++ 1.79K 2010-03-04 21:14:24 .
蝴蝶的1k一定是因為另有正解!
怪噁心的Heap= =
#include<stdio.h>
#include<algorithm>
#define MAX 30010
int n,pos,ary[MAX*2],cnt,np,bcnt;
bool fl;
struct skyline{
int hei[MAX],pos[MAX],rear;
void init(){
rear=hei[0]=0;
pos[0]=1;
}
void push(int x,int y){
if(pos[rear]==x){
if(hei[rear]<y)
hei[rear]=y;
}
else if(hei[rear]!=y){
hei[++rear]=y;
pos[rear]=x;
}
}
}s;
struct ele{
int l,r,h;
bool operator<(const ele &b)const{
return h<b.h;
}
inline void get(){
scanf("%d%d%d",&l,&h,&r);
ary[cnt++]=l;
ary[cnt++]=r;
}
}e[MAX];
bool cmp(ele a,ele b){
return a.l<b.l;
}
struct heap{
ele ar[MAX],t;
int rear;
void ch(int a,int b){
t=ar[a];
ar[a]=ar[b];
ar[b]=t;
}
void upset(int n){
if(n<2||n>=rear)return;
int t=n/2;
if(ar[t]<ar[n]){
ch(t,n);
upset(t);
}
}
void downset(int n){
if(n<1||n>=rear)return;
int t=n<<1,opt;
if(t<rear&&ar[n]<ar[t]){
opt=t+1<rear&&ar[t]<ar[t+1];
ch(t+opt,n);
downset(t+opt);
}
else if(t+1<rear&&ar[n]<ar[t+1]){
ch(t+1,n);
downset(t+1);
}
}
void push(ele a){
ar[rear]=a;
upset(rear++);
}
void pop(){
if(rear<2)return;
ch(1,--rear);
downset(1);
}
}h;
int main(){
while(scanf("%d",&n),n){
s.init();
h.rear=1;
bcnt=cnt=np=fl=0;
for(int i=0;i<n;i++)
e[i].get();
std::sort(e,e+n,cmp);
std::sort(ary,ary+cnt);
e[n].l=0;e[n].r=ary[cnt-1]+1;e[n].h=0;
h.push(e[n]);
for(int i=0;i<cnt;){
pos=ary[i];
for(;bcnt<n&&e[bcnt].l<=pos;bcnt++)
h.push(e[bcnt]);
while(h.ar[1].r<=pos)
h.pop();
s.push(pos,h.ar[1].h);
while(i<cnt&&ary[i]==pos)i++;
}
for(int i=0;i<=s.rear;i++){
if(s.pos[i]==1&&s.hei[i]==0)continue;
if(fl)putchar(32);
printf("%d %d",s.pos[i],s.hei[i]);
fl=1;
}
putchar('\n');
}
}
沒有留言:
張貼留言