Pagini recente » Cod sursa (job #1143535) | Cod sursa (job #2458059) | Cod sursa (job #1289995) | Cod sursa (job #2144921) | Cod sursa (job #2271068)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,maxi,st,dr,mid,sol;
int d[100001];
struct numar
{
int st,dr;
}t[100001];
int criteriu(numar a,numar b){
if(a.dr==b.dr)
return(a.st<b.st);
return(a.dr<b.dr);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>t[i].st>>t[i].dr;
sort(t+1,t+n+1,criteriu);
d[1]=t[1].dr-t[1].st;
for(int i=2;i<=n;i++)
{
d[i]=max(t[i].dr-t[i].st,d[i-1]);
if(t[i].st>=t[i-1].dr)
d[i]=d[i-1]+t[i].dr-t[i].st;
st=1;
dr=i-1;
sol=0;
while(st<=dr)
{
mid=(st+dr)/2;
if(t[mid].dr<=t[i].st)
{
sol=mid;
st=mid+1;
}
else
dr=mid-1;
}
if(sol!=0)
d[i]=max(d[i],d[sol]+t[i].dr-t[i].st);
}
maxi=0;
for(int i=1;i<=n;i++)
if(d[i]>maxi)
maxi=d[i];
fout<<maxi;
return 0;
}