Pagini recente » Cod sursa (job #2592274) | Cod sursa (job #10832) | Cod sursa (job #1555020) | Cod sursa (job #1141579) | Cod sursa (job #522239)
Cod sursa(job #522239)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct intz
{
int st,dr;
};
bool ver2(intz x,intz y)
{
if(x.dr==y.dr)
return (x.st>y.st);
return (x.dr<y.dr);
}
intz a[100100];
int sol[100100];
bool ver(int x,int i)
{
return (a[x].dr<=a[i].st);
}
void bs (int i)
{
int st=0,dr,last=0,med;
dr=i-1;
while(st<=dr)
{
med=st+((dr-st)>>1);
if(ver(med,i))
{
last=med;
st=med+1;
}
else
dr=med-1;
}
sol[i]=sol[last]+a[i].dr-a[i].st;
if(sol[i]<sol[i-1])
sol[i]=sol[i-1];
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].st,&a[i].dr);
sort(a+1,a+n+1,ver2);
sol[1]=a[1].dr-a[1].st;
for(i=2;i<=n;i++)
bs(i);
printf("%d",sol[n]);
return 0;
}