Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:谁帮我检查一下 一定重谢

Posted by hzsmajia at 2007-09-27 20:06:27 on Problem 3277
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: