poj 3277 City Horizon

http://poj.org/problem?id=3277
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 500000
  5 using namespace std;
  6 
  7 typedef __int64 ll;
  8 ll a[maxn],b[maxn],ans;
  9 struct node
 10 {
 11     ll a,b,h;
 12     bool operator <(const node &a)const
 13     {
 14         return h<a.h;
 15     }
 16 }p[maxn];
 17 
 18 struct node1
 19 {
 20     int l,r;
 21     ll h;
 22     bool operator <(const node1 &a)const
 23     {
 24         return h<a.h;
 25     }
 26 }tree[4*maxn];
 27 
 28 void build(int i,int l,int r)
 29 {
 30     tree[i].l=l;
 31     tree[i].r=r;
 32     tree[i].h=0;
 33     if(l+1==r) return;
 34     int mid=(l+r)>>1;
 35     build(i<<1,l,mid);
 36     build(i<<1|1,mid,r);
 37 }
 38 
 39 int bs(int l,int r,int key)
 40 {
 41     int low=l,high=r;
 42     while(low<=high)
 43     {
 44         int mid=(low+high)>>1;
 45         if(b[mid]==key)
 46             return mid;
 47         else if(b[mid]<key)
 48             low=mid+1;
 49         else
 50             high=mid-1;
 51     }
 52 }
 53 
 54 void insert1(int i,int l,int r,int h)
 55 {
 56     if(h<tree[i].h) return ;
 57     if(tree[i].l==l&&tree[i].r==r)
 58     {
 59         tree[i].h=h;
 60         return ;
 61     }
 62     if(tree[i].h>=0&&tree[i].r>tree[i].l+1)
 63     {
 64         tree[i<<1].h=tree[i<<1|1].h=tree[i].h;
 65         tree[i].h=-1;
 66     }
 67     int mid=(tree[i].l+tree[i].r)>>1;
 68     if(r<=mid)
 69     {
 70         insert1(i<<1,l,r,h);
 71     }
 72     else if(l>=mid)
 73     {
 74         insert1(i<<1|1,l,r,h);
 75     }
 76     else
 77     {
 78         insert1(i<<1,l,mid,h);
 79         insert1(i<<1|1,mid,r,h);
 80     }
 81 
 82 }
 83 
 84 void sum(int i)
 85 {
 86     if(tree[i].h>=0)
 87     {
 88         //*if(tree[i].h>0)
 89             //printf("%lld
",tree[i].h*(b[tree[i].r]-b[tree[i].l]));
 90         ans+=(tree[i].h*(b[tree[i].r]-b[tree[i].l]));
 91         //return ans;
 92     }
 93     else{
 94         sum(i<<1);
 95         sum(i<<1|1);
 96     }
 97 }
 98 
 99 int main()
100 {
101     int N;
102     while(scanf("%d",&N)!=EOF)
103     {
104         int t1=0;
105         for(int i=0; i<N; i++)
106         {
107             scanf("%I64d%I64d%I64d",&p[i].a,&p[i].b,&p[i].h);
108             a[t1++]=p[i].a;a[t1++]=p[i].b;
109         }
110         sort(a,a+2*N);
111         b[0]=a[0];
112         int t=1;
113         sort(p,p+N);
114         for(int i=1; i<t1; i++)
115         {
116             if(a[i]!=a[i-1])
117             {
118                 b[t++]=a[i];
119             }
120         }
121         build(1,0,t-1);
122         ans=0;
123         for(int i=0; i<N; i++)
124         {
125             int x=bs(0,t-1,p[i].a);
126             int y=bs(0,t-1,p[i].b);
127             insert1(1,x,y,p[i].h);
128         }
129         sum(1);
130         printf("%I64d
",ans);
131     }
132     return 0;
133 }
View Code