1003.cpp

ACM1000_1010竞赛的赛题,源码

//716 2003-05-24 13:27:23 Accepted 1003 C++ 00:00:19 540K just for play 
#include<stdio.h>
#include<string.h>

struct segtype
{
	int from,to,color;
};

int main()
{
//	freopen("1003.in","r",stdin);
//	freopen("1003.out","w",stdout);
	segtype seg[8000];	
	int n;int seg_cnt;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j;		
		int tfrom,tto,tc;
		seg_cnt=0;
		for(i=0;i<n;i++)
		{
			scanf("%d%d%d",&tfrom,&tto,&tc);			
			int has_set=false;
			for(j=0;j<seg_cnt;j++)
			{
				if(tfrom>seg[j].from&&tto<seg[j].to)
				{					
					seg[seg_cnt].from=tto;
					seg[seg_cnt].to=seg[j].to;
					seg[seg_cnt].color=seg[j].color;
					seg_cnt++;
					seg[j].to=tfrom;
					continue;
				}
				if(tfrom>seg[j].from&&tfrom<seg[j].to)
					seg[j].to=tfrom;
				if(tto>seg[j].from&&tto<seg[j].to)
					seg[j].from=tto;
				if(tfrom<=seg[j].from&&tto>=seg[j].to)
				{
					if(!has_set)
					{
						has_set=true;
						seg[j].from=tfrom;seg[j].to=tto;
						seg[j].color=tc;
					}
					else
					{
						seg[j]=seg[seg_cnt-1];
						seg_cnt--;
						j--;
					}
				}
				
			}
			if(!has_set)
			{
				seg[seg_cnt].from=tfrom;
				seg[seg_cnt].to=tto;
				seg[seg_cnt].color=tc;
				seg_cnt++;
			}
			
		}

		int color[8001];
		int segcol[8001];
		memset(segcol,0xff,sizeof(segcol));
		memset(color,0,sizeof(color));		
		for(i=0;i<seg_cnt;i++)
		{
			for(j=seg[i].from;j<seg[i].to;j++)
				segcol[j]=seg[i].color;
		}
		int pre=-1;
		for(i=0;i<8001;i++)
		{
			if(segcol[i]>=0)
			{
				if(segcol[i]!=pre){	color[segcol[i]]++;pre=segcol[i];}
			}
			else	pre=-1;
		}
		for(i=0;i<8001;i++)
			if(color[i])	printf("%d %d\n",i,color[i]);
		printf("\n");
	}
	return 0;
}