● 1003 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: Program
标  题: 1003
发信站: 荔园晨风BBS站 (Sun May 25 10:18:31 2003), 站内信件

//把染色顺序反过来，然后直接用基本的线段树的插入就行了
//ZOJ Monthly, May 2003 Contest 1003
//Count the Colors
#include <stdio.h>
#include <string.h>

int color[20000],flag[9000],deg[9000];

void insert(int minx,int maxx,int x1,int x2,int k,int c)
{
        int mid;
        if (x1<=minx&&x2>=maxx){
                color[k]=c;
                return;
        }
        if (color[k]==c) return;
        mid=(minx+maxx)/2;
        if (color[k]>0){
                color[2*k+1]=color[k];
                color[2*k+2]=color[k];
        }
        color[k]=-1;
        if (x1<=mid) insert(minx,mid,x1,x2,2*k+1,c);
        if (x2>mid)  insert(mid+1,maxx,x1,x2,2*k+2,c);
}

int find(int x1,int x2,int x,int k)
{
        int t;
        if (color[k]>=0) return color[k];
        t=(x1+x2)/2;
        if (x<=t)       return find(x1,t,x,2*k+1);
        else            return find(t+1,x2,x,2*k+2);
}

int main()
{
        int i,n,x1,x2,c,pre;
//      freopen("1003.in","r",stdin);
        while(scanf("%d",&n)!=EOF){
                memset(color,0,sizeof(color));
                for(i=0;i<n;i++){
                        scanf("%d%d%d",&x1,&x2,&c);
                        x2--;
                        c++;
                        if (x1<=x2) insert(0,8000,x1,x2,0,c);
                }
                pre=find(0,8000,0,0);
                memset(flag,0,sizeof(flag));
                for(i=1;i<=8000;i++){
                        c=find(0,8000,i,0);
                        if (c!=pre){
                                if (pre>0) flag[pre]++;
                                pre=c;
                        }
                }
                for(i=1;i<=8000;i++) if (flag[i]>0) printf("%d %d\n",i-1,flag[i]
);
                printf("\n");
        }
        return 0;
}

--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 修改:·huhaiming 於 May 26 09:57:46 修改本文·[FROM: 192.168.0.200]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店