Cod sursa(job #730523)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 6 aprilie 2012 13:42:54
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
#define LE 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval {int x,y;}v[LE],a[LE];
int i,n,pozitie,timp,k,MAX ;

int comp(interval e ,interval c){
	if (e.y==c.y) return e.x<c.x;
	return e.y<c.y;
}


int caut(int val){
	int step,poz;
	for(step=1;step<=k;step*=2);

	for(poz=0;step;step/=2)
		if (poz+step<=k&&a[poz+step].y<=val) 
			poz+=step;
		
	return poz;
}


int main(){
    f>>n;
	for(i=1;i<=n;++i) f>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,comp);
	
	for(i=1;i<=n;++i){
		pozitie=caut(v[i].x);
		
		timp=a[pozitie].x+v[i].y-v[i].x;
		
		if (a[k].x<timp&&a[k].y==v[i].y) a[k].x=timp;
		
		if (a[k].x!=v[i].y) 
		    {a[++k].x=timp;a[k].y=v[i].y;}
	}
	
	for(i=1;i<=k;++i) 
		if (a[i].x>MAX) MAX=a[i].x;
	g<<MAX<<'\n';
	
	f.close();g.close();
	return 0;
}