infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
poj 2528Mayor's posters
http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
离散化+线段树

Source Code

Problem: 2528
User: lovecanon
Memory: 760K
Time: 79MS
Language: C++
Result: Accepted

  • Source Code

#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int tree[20002*3+1],seg[20002][2],a[20002],point[20002],vis[20002],tot,sum_of_point,size;

int min(int a,int b){if(a<=b) return a;else return b;}
int max(int a,int b){if(a>=b) return a;else return b;}

int cmp(const void *a,const void *b){
    
return *(int *)a-*(int *)b;
}
int binary_search(int t){
    
int l=1,r=sum_of_point;
    
while(l<=r){
        
int m=(l+r)/2;
        
if(point[m]==t) return m;
        
else if(point[m]>t) r=m-1;
        
else l=m+1;
    }
    
return l;
}
void modify(int l,int r,int c,int L,int R,int t){
    
if(l==L&&r==R||tree[t]==c) {tree[t]=c;return ;} 
    
if(tree[t]!=-1) tree[t*2]=tree[t*2+1]=tree[t];
    tree[t]
=-1;
    
int m=(L+R)/2;
    
if(l<m) modify(l,min(m,r),c,L,m,t*2);
    
if(r>m) modify(max(l,m),r,c,m,R,t*2+1);
}
void query(int t,int L,int R){
    
if(tree[t]!=-1&&tree[t]!=0){
        
int i;
        
for(i=L;i<R;i++) a[i]=tree[t];
    }
    
else if(tree[t]!=0){
        query(t
*2,L,(L+R)/2);
        query(t
*2+1,(L+R)/2,R);    
    }
}
int main(){
    
int i,T,N,x,y;
    scanf(
"%d",&T);
    
while(T--){
        scanf(
"%d",&N);
        tot
=0;
        
for(i=1;i<=N;i++){
            scanf(
"%d%d",&x,&y);
            seg[i][
0]=x;seg[i][1]=y+1;
            a[
++tot]=x;a[++tot]=y+1;
        }
        qsort(a
+1,tot,sizeof(a[0]),cmp);
        sum_of_point
=0;point[++sum_of_point]=a[1];
        
        
for(i=2;i<=tot;i++)
            
if(a[i]!=a[i-1]) point[++sum_of_point]=a[i];

  
        size
=sum_of_point;
        tree[
1]=0;
        
for(i=1;i<=N;i++){
            x
=binary_search(seg[i][0]);
            y
=binary_search(seg[i][1]);
            modify(x,y,i,
1,size,1);
        }
        memset(a,
0,sizeof(a));
        memset(vis,
0,sizeof(vis));
        query(
1,1,size);
        
int tmp=-2,ret=0;
        
for(i=1;i<size;i++){
            
if(a[i]==tmp) continue;
            
else{
                tmp
=a[i];
                
if(tmp!=0&&!vis[tmp]) {vis[tmp]=1;ret++;}
            }
        }
        printf(
"%d\n",ret);
    }
    
return 0;
}

posted on 2008-10-18 18:46 infinity 阅读(459) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理