Pagini recente » Cod sursa (job #2433053) | Cod sursa (job #66066) | Cod sursa (job #223385) | Cod sursa (job #1888037) | Cod sursa (job #1221657)
#include <fstream>
#include <algorithm>
const char IN [ ] = "heavymetal.in" ;
const char OUT [ ] = "heavymetal.out" ;
const int MAX = 100014 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
struct hm {
int x , y ;
};
hm q [ MAX ] ;
bool cmp ( hm a , hm b )
{
return a.y < b.y ;
}
int din [ MAX ] ;
int caut ( int st , int dr , int val )
{
int last = -1 ;
while ( st <= dr )
{
int mij = ( st + dr ) >> 1 ;
if ( q [ mij ].y <= val )
{
last = mij ;
st = mij + 1 ;
}
else dr = mij - 1 ;
}
return last ;
}
int main( )
{
int n ;
fin >> n ;
for ( int i = 1 ; i <= n ; ++ i )
fin >> q [ i ].x >> q [ i ].y ;
sort ( q + 1 , q + n + 1 , cmp ) ;
din [ 1 ] = q [ 1 ].y - q [ 1 ].x ;
for ( int i = 2 ; i <= n ; ++ i )
{
int poz = caut ( 1 , i - 1 , q [ i ].x ) ;
din [ i ] = din [ i - 1 ];
if ( poz == - 1 )
din [ i ] = max ( din [ i ] , q [ i ].y - q [ i ].x ) ;
else din [ i ] = max ( din [ i ] , din [ poz ] + q [ i ].y - q [ i ].x ) ;
}
fout << din [ n ] ;
return 0;
}