1201.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

const int size = 50010;

int p[size], s[size];
int m;

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

void set( int y )
{
	int j;

	y++;

	for(j=y;j<=m;j+=lowbit(j))
		s[j]++;

}

int count(int y)
{
	int ans=0,j;
	y++;

	for(j=y;j>0;j-=lowbit(j))
		ans+=s[j];

	return ans;
}

int x[size], y[size], c[size], n;
int id[size];

bool cmp( int a, int b )
{
	return y[a] < y[b];
}

void init( )
{
	int i;
	memset( p, -1, sizeof p );
	memset( s, 0, sizeof s );

	scanf( "%d", &n );

	for( i=0; i<n; i++ )
	{
		scanf( "%d %d %d", &x[i], &y[i], &c[i] );
		id[i] = i;
	}
	sort( id, id+n, cmp );

	m = y[id[n-1]] + 5;
}

int st[size], sn;

void doit( )
{
	int a, b, i, k, h, l;
	
	for( k=0; k<n; k++ )
	{
		a = x[ id[k] ];
		b = y[ id[k] ]+1;
		l = c[ id[k] ];
		h = count( b ) - count( a );
		
		if( h < l )
		{
			sn = 0;
			for( i=b; h<l; h++ )
			{
				while( p[i] != -1 )
				{
					st[sn++] = i;
					i = p[i];
				}
				set( i );
				st[sn++] = i;
				i--;
			}

			while( sn-- )
				p[ st[sn] ] = i;
		}
	}

	printf( "%d\n", count( m ) );
}

int main( )
{
	init( );
	doit( );
	return 0;
}