Cod sursa(job #794688)

Utilizator visanrVisan Radu visanr Data 6 octombrie 2012 20:27:51
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define ll long long
#define nmax 100010

struct data
{
    ll S, E;
}V[nmax];
long long N, ans[nmax];

bool cmp(data one, data two)
{
    return one.E < two.E;
}

ll BS(ll Val)
{
    ll left = 1, right = N, mid, now = 0;
    while(left <= right)
    {
        mid = left + (right - left) / 2;
        if(V[mid].E <= Val)
        {
            now = mid;
            left = mid + 1;
        }else
        {
            right = mid - 1;
        }
    }
    return now;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    scanf("%i", &N);
    for(int i = 1; i <= N; i++) scanf("%lld %lld", &V[i].S, &V[i].E);
    sort(V + 1, V + N + 1, cmp);
    ans[1] = V[1].E - V[1].S;
    for(int i = 2; i <= N; i++)
        ans[i] = max(ans[i - 1], BS(V[i].S) + V[i].E - V[i].S);
    printf("%lld\n", ans[N]);
    return 0;
}