Cod sursa(job #177704)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 13 aprilie 2008 15:12:17
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<stdio.h> 
#include<stdlib.h>
#include<algorithm>
#define N 100010  
using namespace std;
struct interval{  
    int a,b;  
};
interval v[N];
int pozz[N];
struct timp{
	int cost,ora;
};
timp best[N];
inline int compar(struct interval aa,struct interval bb){  
	if (aa.b<bb.b)  
		return -1;  
	if (aa.b>bb.b)  
		return 1;  
	if (aa.a>bb.a)  
		return 1;  
	if (aa.a<bb.a)  
		return -1;  
	return 0;  
}  
//int compara(const void *x,const void*y){
	//return compar(&v[*(int*)x],&v[*(int*)y]);
//}
int f_comp(interval x,interval y){
	return x.a<y.a;
}
int caut(int p,int u,int x,int n){
	int m;
	while(p<u){
		m=(p+u)/2;
		if(x<=best[m].ora)
			u=m;
		else
			p=m+1;
	}
	if(best[p].ora>x)
		--p;
	return p;
}
void swap(int i,int j){
     int aux;
     aux=pozz[i];
     pozz[i]=pozz[j];
     pozz[j]=aux;
}
void down_heap(int i,int n,int h[]){
     int max=i;
     if (2*i<=n && compar(v[h[max]],v[h[2*i]])<0)
        max=2*i;
     if (2*i+1<=n && compar(v[h[max]],v[h[2*i+1]])<0)
        max=2*i+1;
     if (max!=i){
        swap(max,i);
        down_heap(max,n,h);
     }
}
void sort(int x){
     int i;
     for (i=x/2;i>=1;--i)
         down_heap(i,x,pozz);
     for (i=x;i>1;--i){
         swap(1,i);
         down_heap(1,i-1,pozz);
     }
     for (i=1;i<=x;++i)
         pozz[i-1]=pozz[i];
}
int main(){  
	int n,i,s=0,t,j,x,m=0;
	int poz,p,u,b[N]={0};
	freopen("heavymetal.in","r",stdin);  
	freopen("heavymetal.out","w",stdout);  
	scanf("%d",&n);  
	for (i=0;i<n;++i){  
		scanf("%d%d",&v[i].a,&v[i].b);  
		pozz[i+1]=i;
	}
	//sort(v,v+n,f_comp);
	//qsort(pozz,n,sizeof(pozz[0]),compara);
	sort(n);
    best[m].cost=v[pozz[0]].b-v[pozz[0]].a;
	best[m++].ora=v[pozz[0]].b;
	for(i=1;i<n;++i){
		poz=caut(0,m-1,v[pozz[i]].a,m);//best[poz].ora va fi cea mai mare ora inainte de v[i].a
		if(v[pozz[i]].b==best[m-1].ora){
			if(best[poz].cost+v[pozz[i]].b-v[pozz[i]].a>best[m-1].cost)
				best[m-1].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
		}
		else
			if(best[poz].cost+v[pozz[i]].b-v[pozz[i]].a>best[m-1].cost){
				best[m].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
				best[m++].ora=v[pozz[i]].b;
			}
	}
	printf("%d\n",best[m-1].cost);
	return 0;  
}