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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

USACO的数据都过了,难道POJ加了数据。。。WAing。。。

Posted by yogafrank at 2008-11-02 00:04:37 on Problem 3277 and last updated at 2008-11-02 21:41:58
#include <iostream>
#include <algorithm>
using namespace std;

const int SIZE = 40002;
int pos[SIZE * 2], n, tmp[SIZE * 2];

typedef struct node
{
	int s, e;
	int h;

	node()
	{ s = e = h = 0; }
}Node;

Node points[SIZE];

class SegmentTree
{
public:
	Node nodes[SIZE * 6];
public:
	void buildtree( int, int, int );
	void update( int, int, int, int );
	__int64 getresult( int, int, int, int );
};

void SegmentTree::buildtree( int root, int s, int e )
{
	nodes[root].s = s;
	nodes[root].e = e;
	nodes[root].h = 0;

	if( e - s  > 1 )
	{
		int mid = ( s + e ) / 2;
		buildtree( root * 2, s, mid );
		buildtree( root * 2 + 1, mid, e );
	}
}

void SegmentTree::update( int root, int s, int e, int h )
{
	if( nodes[root].h > h )
		return;

	if( s <= nodes[root].s && nodes[root].e <= e )
	{
		nodes[root].h = h;
		return;
	}

	if( nodes[root].e - nodes[root].s == 1 )
		return;

	int mid = ( nodes[root].s + nodes[root].e ) / 2;
	if( s < mid )
		update( root * 2, s, e, h );
	if( mid < e )
		update( root * 2 + 1, s, e, h );
}

__int64 SegmentTree::getresult( int root, int s, int e, int maxv )
{
	if( maxv < nodes[root].h )
		maxv = nodes[root].h;

	if( nodes[root].e - nodes[root].s == 1 )
		return (__int64) maxv * ( pos[nodes[root].e] - pos[nodes[root].s] );

	__int64 r = 0;
	int mid = ( nodes[root].s + nodes[root].e ) / 2;
	if( mid <= s )
		r += getresult( root * 2 + 1, s, e, maxv );
	else if( mid >= e )
		r += getresult( root * 2, s, e, maxv );
	else
	{
		r += getresult( root * 2, s, mid, maxv );
		r += getresult( root * 2 + 1, mid, e, maxv );
	}

	return r;
}

int find( int n, int v )
{
	int low = 1, high = n, mid;

	while( low < high )
	{
		mid = ( low + high ) / 2;
		if( pos[mid] < v )
			low = mid + 1;
		else
			high = mid;
	}
	
	return high;
}

SegmentTree tree;


int main()
{
	int num = 1, i, count;
	scanf( "%d", &n );
	for( i = 1; i <= n; i++ )
	{
		scanf( "%d%d%d", &points[i].s, &points[i].e, &points[i].h );
		tmp[num++] = points[i].s;
		tmp[num++] = points[i].e;
	}

	num--;
	sort( tmp + 1, tmp + 1 + num );
	pos[1] = tmp[1];
	for( i = count = 2; i <= num; i++ )
	{
		if( tmp[i] != tmp[i - 1] )
			pos[count++] = tmp[i];
	}

	count--;
	tree.buildtree( 1, 1, count );
	for( i = 1; i <= n; i++ )
	{
		int l = find( count, points[i].s );
		int r = find( count, points[i].e );
		
		tree.update( 1, l, r, points[i].h );
	}

	printf( "%I64d\n", tree.getresult( 1, 1, count, 0 ) );

	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