Cod sursa(job #138767)

Utilizator vlad_DVlad Dumitriu vlad_D Data 19 februarie 2008 05:49:34
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int N;
vector<pair<int, int> > P;
vector<int> Q;
map<int, int> O;
int DP[200001];

int main() 
{
//	freopen("heavymetal.in", "r", stdin);
	//freopen("heavymetal.out", "w", stdout);
	
	int i, j;
	scanf("%d", &N);
	for (i = 0; i < N; ++i)
	{		
		int a, b;
		scanf("%d %d", &a, &b);
		if (!O[a]) Q.push_back(a), O[a] = 1;
		if (!O[b-1]) Q.push_back(b-1), O[b-1] = 1;
		P.push_back(make_pair(a, b-1));		
	};

	sort(Q.begin(), Q.end());
	
	for (i = 0; i < Q.size(); ++i) O[Q[i]] = i+1;
	
	for (i = 0; i < P.size(); ++i) P[i].first = O[P[i].first],
	P[i].second = O[P[i].second];
	for (i = 0; i < P.size(); ++i) swap(P[i].first, P[i].second);
	sort(P.begin(), P.end());
	for (i = 0; i < P.size(); ++i) swap(P[i].first, P[i].second);
	int best = 0;
	int k = 0;
	for (i = 1; i <= Q[Q.size()-1]; ++i) 
	{
		DP[i] = DP[i-1];
		for (; k < P.size() && P[k].second == i; ++k) 
			if (DP[P[k].first-1] + Q[P[k].second-1] - Q[P[k].first-1] + 1 > DP[i]) 
				DP[i] = DP[P[k].first-1] + Q[P[k].second-1] - Q[P[k].first-1] + 1;
		if (DP[i] > best) best = DP[i];
	};
	printf("%d", best);
 	return 0;	
};