Cod sursa(job #1692131)

Utilizator isa_fares_mudiFares Mohamad isa_fares_mudi Data 20 aprilie 2016 10:44:55
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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 ) {
        if ( v[i].x > v[1].y ) {
            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 );

        }
        else
            d[i] = max ( v[i].y-v[i].x, my_max );
        if( d[i] > my_max )
            my_max = d[i];
    }
    printf ( "%d", my_max );
    return 0;
}