Pagini recente » Cod sursa (job #348450) | Cod sursa (job #1742591) | Cod sursa (job #1769826) | Cod sursa (job #1380595) | Cod sursa (job #137315)
Cod sursa(job #137315)
#include<stdio.h>
#define NMAX 100000
long s,rr,ll,i,n,l[NMAX],r[NMAX];
long part(long st,long dr)
{
long x,m,p,i,j;
m=(st+dr)/2;
p=l[m];
i=st-1;
j=dr+1;
while(1)
{
do{i++;}while(l[i]<p||(l[i]==p&&r[i]<r[m])) ;
do{j--;}while(l[j]>p||(l[j]==p&&r[j]>r[m])) ;
if(i<j)
{
x=l[i];
l[i]=l[j];
l[j]=x;
x=r[i];
r[i]=r[j];
r[j]=x;
}
else return j;
}
}
void quick(long st,long dr)
{
long sep;
if(st<dr)
{
sep=part(st,dr);
quick(st,sep);
quick(sep+1,dr);
}
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;++i)
scanf("%ld %ld",&l[i],&r[i]);
quick(1,n);
ll=l[1];
rr=r[1];
s=s+rr-ll;
for(i=2;i<=n;++i)
{
if(l[i]==ll)
{
if(r[i]-l[i]>rr-ll)
{
s+=(r[i]-l[i])-(rr-ll);
ll=l[i];
rr=r[i];
}
}
else
{
if(l[i]>=rr)
{
ll=l[i];
rr=r[i];
s+=rr-ll;
}
}
}
printf("%ld",s);
return 0;
}