Pagini recente » Istoria paginii runda/ag/clasament | Borderou de evaluare (job #1410367) | Cod sursa (job #1032956) | Istoria paginii runda/pgleague | Cod sursa (job #1517096)
/*
Cautam binar cel mai din dreapta interval care capatul din dreapta mai mic sau egal decat capatul din stanga al intervalului curent
*/
#include <fstream>
#include <cstdio>
#include <algorithm>
#define NMax 100002
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int A[NMax],B[NMax],Best[NMax],i;
int TMax;
struct coada
{
int x,y;
}V[NMax];
bool cmp(coada i,coada j)
{
return i.y<j.y;
}
int main()
{
int n,x,y,sol;
fin>>n;
for( i=1;i<=n;i++)
{
fin>>V[i].x>>V[i].y;
}
sort(V+1,V+n+1,cmp);
Best[1]=V[1].y-V[1].x;
sol=Best[1];
for( i=2;i<=n;i++)
{
Best[i]=Best[i-1];
int s=1;
int d=i-1;
int j=0;
while(s<=d)
{
int mij=(s+d)/2;
if(V[mij].y<=V[i].x)
{
j=mij;
s=mij+1;
}
else
d=mij-1;
}
Best[i]=max(Best[i],Best[j]+V[i].y-V[i].x);
}
for(i=1;i<=n;i++)
{
sol=max(sol,Best[i]);
}
fout<<sol<<"\n";
}