Cod sursa(job #446843)

Utilizator c912045Marcu Florian c912045 Data 26 aprilie 2010 19:34:00
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
using namespace std;
#include<fstream>
#include<algorithm>
#include<vector>
#define mk make_pair
#define x first
#define y second
const int MAX_N = 100007;
pair<int, int> A[MAX_N], B[MAX_N];
int N, bst[MAX_N], V[MAX_N*2], P, H[2*MAX_N];
vector<int>G[2*MAX_N];
struct cmp
{
	bool operator()(const pair<int, int> &a, const pair<int, int> &b)const
	{
		return (a.y == b.y)?( a.x < b.x ):(a.y < b.y);
	}
};
int main()
{
	ifstream in("heavymetal.in"); ofstream out("heavymetal.out");
	int i, j, a, b, k;
	in>>N;
	for(i = 1; i <= N; ++i)
	{
		in>>a>>b;
		A[i] = mk(a,b);
		H[++P] = a, H[++P] = b;
	}
	sort( A + 1, A + N + 1, cmp());
	sort( H + 1, H + P + 1 );
	V[1] = 1;
	for(i = 2, P = 1; i <= 2*N; ++i)
		if( H[i] != H[i-1] ) V[++P] = H[i];
	for(i = 1; i <= N; ++i)
	{
		a = lower_bound( V + 1, V + P + 1, A[i].x ) - V;
		b = lower_bound( V + 1, V + P + 1, A[i].y ) - V;
		B[i] = mk(a,b);
		G[b].push_back(i);
	}
	for(i = 1; i <= 2*N; ++i)
	{
		bst[i] = bst[i-1];
		for(k = 0; k < G[i].size(); ++k)
		{
			j = G[i][k];
			bst[i] = max( bst[i], bst[ B[j].x ] + A[j].y - A[j].x );
		}
	}
	out<<bst[2*N]<<"\n";
	return 0;
}