Cod sursa(job #595346)

Utilizator veleanduAlex Velea veleandu Data 11 iunie 2011 22:41:03
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
# define maxn 100005
using namespace std;
typedef struct { long st,dr; } interval;
interval T[maxn];
long REZ[maxn];
long i,j,n;
long maxim,poz,maxim2;
long BS ( int val ) {
    int i, cnt ;
    for (cnt = 1; cnt << 1 <= n; cnt <<= 1) ;
    for (i = 0; cnt; cnt >>= 1) 
        if (i + cnt <= n && T[i + cnt].st < val) 
           i += cnt ; 
    return i ;
}

bool mysort ( interval a, interval b)
{
	if ( a.st > b.st )
		return 0;
	if ( a.st < b.dr )
		return 1;
	if ( a.dr < b.dr )
		return 0;
	return 1;
}
int main()
{
	ifstream in("heavymetal.in");
	ofstream out("heavymetal.out");
	in>>n;
	for ( i=1; i<=n; ++i )
		in>>T[i].st>>T[i].dr;
	sort(T+1,T+n+1,mysort);
	for ( i=1; i<=n; ++i )
	{
		if ( REZ[i]>maxim)
			maxim=REZ[i];
		if ( maxim+T[i].dr-T[i].st > maxim2)
			maxim2=maxim+T[i].dr-T[i].st;
		poz=BS(T[i].dr);
		poz++;
		REZ[poz]=max(REZ[poz],maxim+T[i].dr-T[i].st);
	}
	out<<maxim2<<"\n";
	return 0;
}