Home > OI > Poj 3277

Poj 3277


一开始以为这道题不需要传递参数,后来发现我错了..比如,先插入线段12 40 11,再插入13 40 13,若不传递参数,那么12~13这一段就会被无视

范围很大,要离散化;注意结果可能超int;区间划分时要注意

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 100001 #define MAXP 200001 #define MAXT 400001 struct segment{     int x,y,h; } seg[MAXN]; struct Point{     int x,id1,id2; } point[MAXP]; int N,pnum,tot; long long area[MAXT],height[MAXT],change[MAXP]; int cmp(const void *a, const void *b){     segment *x=(segment*)a, *y=(segment*)b;     return x->h-y->h; } int cmp1(const void *a, const void *b){     Point *x=(Point*)a, *y=(Point*)b;     return x->x-y->x; } void add(int p, int l, int r, int x, int y, int h){     if(l==x&&r==y||r-l<=1){         height[p]=h;         area[p]=(change[y]-change[x])*h;         return;     }     int m=l+r>>1;     if(height[p]){         height[p*2]=height[p*2+1]=height[p];         area[p*2]=(change[m]-change[l])*height[p];         area[p*2+1]=(change[r]-change[m])*height[p];     }     height[p]=0;     if(y<=m){         add(p*2,l,m,x,y,h);     }else if(x>=m){         add(p*2+1,m,r,x,y,h);     }else{         add(p*2,l,m,x,m,h);         add(p*2+1,m,r,m,y,h);     }     area[p]=area[p*2]+area[p*2+1]; } int main(){     scanf("%d\n",&N);     for(int i=1;i<=N;++i){         scanf("%d %d %d\n",&seg[i].x,&seg[i].y,&seg[i].h);         point[++pnum].x=seg[i].x;         point[pnum].id1=i;         point[pnum].id2=1;         point[++pnum].x=seg[i].y;         point[pnum].id1=i;         point[pnum].id2=2;     }     qsort(point+1,pnum,sizeof(point[0]),cmp1);     for(int i=1;i<=pnum;++i){         if(point[i].x!=point[i-1].x){             ++tot;             change[tot]=point[i].x;         }         if(point[i].id2==1){             seg[point[i].id1].x=tot;         }else{             seg[point[i].id1].y=tot;         }     }     qsort(seg+1,N,sizeof(seg[0]),cmp);     for(int i=1;i<=N;++i){         add(1,1,tot,seg[i].x,seg[i].y,seg[i].h);     }     printf("%lld\n",area[1]);     return 0; }
Categories: OI Tags: , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: