| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:谁帮我检查一下 一定重谢In Reply To:wa Posted by:hzsmajia at 2007-09-27 20:02:44
#include <stdio.h>
#include <algorithm>
struct H
{
int s, e, h;
}h[40005];
int a[80010];
int m;
struct
{
int l, r, h;
int cov;
__int64 areal, arear, area;
}tree[8*80010];
int s, e;
inline int cmp(H a, H b)
{
return a.h < b.h;
}
void construct(int now, int left, int right)
{
tree[now].l = left;
tree[now].r = right;
tree[now].h = 0;
tree[now].cov = 0;
tree[now].area = 0;
tree[now].areal = 0;
tree[now].arear = 0;
if(left + 1 < right)
{
int mid = (left + right) >> 1;
construct(2*now, left , mid);
construct(2*now+1, mid, right);
}
}
int binsea(int c)
{
int l = 1, r = m;
while(l < r)
{
int mid = (l + r) >> 1;
if(a[mid] >= c) r = mid;
else l = mid+1;
}
return l;
}
__int64 inserttree(int now, int h)
{
int mid = (tree[now].l + tree[now].r) >> 1;
if(s <= tree[now].l && e >= tree[now].r )
{
tree[now].h = h;
tree[now].cov = 1;
// printf("now %d %d\n", now, h);
tree[now].areal = h*(a[mid] - a[tree[now].l]);
tree[now].arear = h*(a[tree[now].r] - a[mid]);
tree[now*2].area = tree[now].areal;
tree[now*2+1].area = tree[now].arear;
tree[now*2].cov = 1;
tree[now*2+1].cov = 1;
return tree[now].area = tree[now].areal + tree[now].arear;
}
if(tree[now].cov == 1)
{
tree[now].areal = tree[now].h*(a[mid] - a[tree[now].l]);
tree[now].arear = tree[now].h*(a[tree[now].r] - a[mid]);
if(tree[now].l + 1 < tree[now].r)
{
tree[now*2].area = tree[now].areal;
tree[now*2+1].area = tree[now].arear;
tree[now*2].cov = 1;
tree[now*2+1].cov = 1;
}
}
tree[now].cov = -2;
if(s < mid) tree[now].areal = inserttree(2*now, h);
if(e > mid) tree[now].arear = inserttree(2*now+1, h);
return tree[now].area = tree[now].areal + tree[now].arear;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("3277.txt","r",stdin);
#endif
int i, n;
scanf("%d", &n);
m = 1;
for(i=0; i < n; i++)
{
scanf("%d %d %d",&h[i].s, &h[i].e, &h[i].h);
a[m++] = h[i].s;
a[m++] = h[i].e;
}
std::sort(a+1, a+m);
std::sort(h, h+n, cmp);
int j = 1;
for(i = 2; i < m; i++)
{
if(a[i] != a[j])
{
j ++;
a[j] = a[i];
}
}
m = j ;
// printf("m %d\n", m);
construct(1, 1, m);
for(i=0; i < n; i++)
{
s = binsea(h[i].s);
e = binsea(h[i].e);
// printf("%d %d\n", s, e);
inserttree(1, h[i].h);
// printf("area %I64d\n", tree[1].area);
}
printf("%I64d\n", tree[1].area);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator