TIOJ 1202 重疊的天際線

 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');
    }
}