Pagini recente » Cod sursa (job #3289425) | Cod sursa (job #2526089) | Cod sursa (job #2776288) | Cod sursa (job #722640) | Cod sursa (job #378538)
Cod sursa(job #378538)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,s,help[100001][2];
struct muzic
{
int val,tip,nra,timp;
};
muzic v[200001];
int cmp (muzic a,muzic b)
{
if(a.val==b.val)
return (a.tip>b.tip);
return(a.val<b.val);
}
int main ()
{
int i,p,nr=0,a,b,poz,n2;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
p=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
v[++nr].val=a;
v[nr].tip=1;
v[nr].nra=++p;
v[++nr].val=b;
v[nr].tip=2;
v[nr].nra=p;
}
n2=2*n;
sort(v+1,v+n2+1,cmp);
for(i=1;i<=2*n;i++)
help[v[i].nra][v[i].tip-1]=i;
s=0;
for(i=1;i<=2*n;i++)
{
if(v[i].tip==1)
{
poz=v[i].nra;
poz=help[poz][1];
v[poz].timp=s+v[poz].val-v[i].val;
}
else
{
if(v[i].timp>s)
s=v[i].timp;
} //else
} //for
printf("%d\n",s);
return 0;
}