Cod sursa(job #1692213)

Utilizator isa_fares_mudiFares Mohamad isa_fares_mudi Data 20 aprilie 2016 14:48:00
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#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;
}