Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator