Cod sursa(job #712124)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 13 martie 2012 06:48:24
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 100001

using namespace std;

struct Interval
{
	Interval() :
		st(0),
		end(0)
	{}
	
	Interval(const int s, const int e) :
		st(s),
		end(e)
	{}
	
	inline bool operator < (const Interval& i) const
	{
		if (end < i.end)
		{
			return true;
		}
		else if (end == i.end)
		{
			return st > i.st;
		}
		
		return false;
	}

	int st, end;
};

unsigned int AirTimes[MAXN];
unsigned int Gains[MAXN];

int FindLastBand(const vector<Interval>& vBands, const int size, const int start)
{
	int step = 1;
	
	while (step <= size)
	{
		step <<= 1;
	}
	
	int i=0;
	for (;step>0; step>>=1)
	{
		if (i+step<=size && vBands[size - i - step].end > start)
		{
			i += step;
		}
	}
	
	return size-i-1;
}

int main()
{
	int n;
	vector<Interval> vBands;
	fstream fin("heavymetal.in", fstream::in);
	fstream fout("heavymetal.out", fstream::out);
	
	fin >> n;
	//cout << n << "\n";
	
	for (int i=0; i<n; ++i)
	{
		int st, end;
		fin >> st >> end;
		
		vBands.push_back(Interval(st,end));
	}
	
	sort(vBands.begin(), vBands.end());
	
	for (int i=0; i<n; ++i)
	{
		Gains[i] = AirTimes[i] = vBands[i].end - vBands[i].st;
		
		//cout << vBands[i].st << " " << vBands[i].end << " " << AirTimes[i] << "\n";
	}
	
	/*int index = FindLastBand(vBands, vBands.size(), 2);
	cout << index << "\n";
	cout << vBands[index].st << " " << vBands[index].end << endl << endl;*/
	
	unsigned int maxTime = 0;
	for (int i=0; i<vBands.size(); ++i)
	{
		int index = FindLastBand(vBands, i, vBands[i].st);
		
		if (index >=0)
		{
			const int ending = vBands[index].end;
			//cout << index << endl;
			while (index >=0)
			{
				Gains[index] = max(Gains[index], AirTimes[index]+Gains[i]);
				maxTime = max(maxTime, Gains[index]);
				index--;
			}
		}
	}
	
	/*for (int i=0; i<n; ++i)
	{
		cout << Gains[i] << " ";
	}
	cout << "\n";*/
	
	fout << maxTime << "\n";
	
	fin.close();
	fout.close();
	return 0;
}