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

## 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: