荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: 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软件 网络书店