UVAOJ 105 - The Skyline Problem

[Heap]

恩 MlogN
是說最近懶得幫他著色了= =

#include<stdio.h>
#include<algorithm>
#include<queue>
#define CM 10010
using namespace std;
class BuildLine
{
public:
    int L,R;
    int H;
    BuildLine():L(0),R(0),H(0){}
    void set(int a,int b,int c)
    {
        L=a,R=b,H=c;
    }
    void Print()const
    {
        printf("Building: (%d %d)=(%d)\n",L,R,H);
    }
};
bool operator< (BuildLine a,BuildLine b)
{
    return (a.H<b.H);
}
bool sortfunc(BuildLine a,BuildLine b)
{
    return (a.L<b.L);
}
priority_queue<BuildLine>Heap;
BuildLine Builds[5050];
int BuildCnt;
int Height[CM+1];
int main()
{
    int a,b,c;
    int Rm=0;
    while(Heap.size())
        Heap.pop();
    BuildCnt=0;
    while(scanf("%d %d %d",&a,&b,&c)!=EOF)
    {
        Builds[BuildCnt++].set(a,c,b);
        if(c>=Rm) Rm=c;
    }
     
    sort(Builds,Builds+BuildCnt,sortfunc);
    int ptr=0;
    for(int lx=1;lx<=CM;lx++)
    {
        while((lx>=Builds[ptr].L)&&(ptr<BuildCnt))
        {
            //Builds[ptr].Print();
            Heap.push(Builds[ptr]);
            ptr++;
        }
        while((Heap.size())&&(lx>=Heap.top().R))
            Heap.pop();
        if(Heap.size())
            Height[lx]=Heap.top().H;
        else
            Height[lx]=0;
        //printf("%d:%d\n",lx,Height[lx]);
    }
    int prev = 0;
    for (int lx=1; lx<Rm; lx++) {
        if (prev==Height[lx]) continue;
        printf("%d %d ",lx,Height[lx]);
        prev = Height[lx];
    }
    printf("%d %d\n",Rm, 0);
    return 0;
}