Pagini recente » Cod sursa (job #882776) | Cod sursa (job #2070197) | Cod sursa (job #3158079) | Cod sursa (job #1108239) | Cod sursa (job #668946)
Cod sursa(job #668946)
#include <fstream>
#include <algorithm>
#define LE 200005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
long long POZ,n,i,TE;
struct two
{
long long x,y;
} T[LE],TMAX[LE];
int cmp(two a,two b)
{
if (a.y==b.y) return b.x<a.x;
return a.y<b.y;
}
long long caut(int val)
{
long long STEP=1,I=0;
for(; STEP<POZ; STEP*=2);
for(; STEP; STEP/=2)
if (TMAX[I+STEP].y<=val&&I+STEP<=POZ) I+=STEP;
return TMAX[I].x;
}
int main()
{
f>>n;
for(i=1; i<=n; i++) f>>T[i].x>>T[i].y;
sort(T+1,T+n+1,cmp);
for(i=1; i<=n; i++)
{
if (T[i-1].y!=T[i].y)
{
POZ++;
TMAX[POZ].y=T[i].y;
}
TMAX[POZ].x=max(TMAX[POZ].x,caut(T[i].x)+(T[i].y-T[i].x));
TE=max(TMAX[POZ].x,TE);
}
g<<TE<<'\n';
f.close();
g.close();
return 0;
}