Pagini recente » Cod sursa (job #672486) | Cod sursa (job #2072519) | Cod sursa (job #2392617) | Cod sursa (job #2039726) | Cod sursa (job #138428)
Cod sursa(job #138428)
#include<stdio.h>
#include<stdlib.h>
struct timp{long timp,interv,dist;};
long n;
timp v[1024*128 *2];
long x[1024*128];
timp w[1024*128 *2];
int cmpstruct ( const void *a, const void *b)
{
return (*(timp *)a).timp - (*(timp *)b).timp;
}
void mergesort(long st,long dr)
{
if( st == dr)
return;
if( st == dr-1)
{
if(v[st].timp > v[dr].timp)
{
timp aux = v[st];
v[st] = v[dr];
v[dr] = aux;
}
return ;
}
long mij = (st + dr)/2;
mergesort(st,mij);
mergesort(mij+1,dr);
long a = st , b = mij+1 ,i = a-1;
for( ; a <= mij && b <= dr; )
{
if( v[a].timp > v[b].timp)
w[++i] = v[b++];
else w[++i] = v[a++];
}
if( a > mij)
{while(b<=dr)
w[++i] = v[b++];}
else
while(a<=mij)
w[++i] = v[a++];
for( long i = a; i<= b; ++i)
v[i] = w[i];
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
for(long i = 1; i <= n; ++i)
{
long a,b;
scanf("%ld %ld",&a,&b);
v[i*2-1].timp = a*2+1;
//v[i*2-1].fel = 1;
v[i*2-1].interv = i;
v[i*2-1].dist = b-a;
v[i*2].timp = b*2;
v[i*2].interv = i;
}
//qsort(v+1,2*n,sizeof(v[0]),cmpstruct);
mergesort(1,2*n);
long max = 0;
for(long i = 1; i <= 2*n; ++i)
{
if( v[i].timp%2 == 1)// intrare
{
x[v[i].interv] = max+ v[i].dist;
}
else
{
if(x[v[i].interv] > max)
max = x[v[i].interv];
}
}
printf("%ld\n",max);
return 0;
}