Cod sursa(job #138763)

Utilizator vlad_DVlad Dumitriu vlad_D Data 19 februarie 2008 05:35:14
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 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];
	sort(P.begin(), P.end());
	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;	
};