Pagini recente » Cod sursa (job #2547567) | Cod sursa (job #2146132) | Cod sursa (job #1771592) | Cod sursa (job #1809401) | Cod sursa (job #1692213)
#include <cstdio>
#include <algorithm>
const int NMAX = 100000;
using namespace std;
struct INT {
int x, y;
}v[NMAX+5];
int d[NMAX+5];
bool cmp ( INT x, INT y ) {
if ( x.y == y.y )
return x.x < y.x;
return x.y < y.y;
}
int main() {
freopen ( "heavymetal.in", "r", stdin );
freopen ( "heavymetal.out", "w", stdout );
int n, st, dr, med, val, my_max;
scanf ( "%d", &n );
for ( register int i = 1 ; i <= n ; ++ i )
scanf ( "%d%d", &v[i].x, &v[i].y );
sort ( v + 1, v + n + 1, cmp );
my_max = 0;
for ( register int i = 1 ; i <= n ; ++ i ) {
st = 1;
dr = i;
val = v[i].x;
while ( st < dr ) {
med = ( st + dr ) / 2;
if( v[med].y <= val )
st = med + 1;
else
dr = med;
}
med = ( st + dr ) / 2;
if ( v[med].y > val )
med--;
d[i] = max ( d[med]+v[i].y-v[i].x, my_max );
if( d[i] > my_max )
my_max = d[i];
}
printf ( "%d", my_max );
return 0;
}