Cod sursa(job #1678405)

Utilizator krityxAdrian Buzea krityx Data 7 aprilie 2016 12:06:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	return a.first < b.first;
}

class AIB
{
	vector<int> _container;
	int leftIndex(int i)
	{
		return (i ^ (i - 1)) & i;
	}
public:
	AIB(int size)
	{
		_container.resize(size + 1, 0);
	}
	void Add(int index, int value)
	{
		for (int i = index; i < _container.size(); i += leftIndex(i))
		{
			_container[i] = max(_container[i], value);
		}
	}
	int Query(int index)
	{
		int mx = 0;
		for (int i = index; i > 0; i -= leftIndex(i))
		{
			mx = max(mx, _container[i]);
		}
		return mx;
	}
};

int main()
{
	ifstream f("heavymetal.in");
	ofstream g("heavymetal.out");
	ios_base::sync_with_stdio(false);

	int n, i, a, b, maxEnd = 0;
	vector<pair<int, int>> v;
	vector<int> best;
	f >> n;
	for (i = 1; i <= n; i++)
	{
		f >> a >> b;
		v.push_back(make_pair(a, b));
		maxEnd = max(maxEnd, b);
	}

	sort(v.begin(), v.end(), cmp);
	best.resize(n);
	AIB aib(maxEnd);

	for (i = 0; i < v.size(); i++)
	{
		best[i] = aib.Query(v[i].first) + (v[i].second - v[i].first);
		aib.Add(v[i].second, best[i]);
	}

	int ans = best[0];
	for (i = 1; i < n; i++)
	{
		ans = max(best[i], ans);
	}
	g << ans;


	return 0;
}