Cod sursa(job #139199)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 februarie 2008 20:10:25
Problema Heavy metal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define maxim(a, b) ((a > b) ? a : b)
#define PII pair<int, int>
#define f first
#define s second
#define NMax 100005

int N, X[NMax<<1], D[NMax<<1], h, bst;
PII C[NMax];
set<int> A;

int cmp_pair(const PII& a, const PII& b)
{ return a.s < b.s; }

int main(void)
{
    int i;
    set<int>::iterator it;
    
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d", &C[i].f, &C[i].s);
        C[i].s--;
        A.insert(C[i].f);
        A.insert(C[i].s);
    }

    for (it = A.begin(); it != A.end(); ++it)
        X[++h] = *it;

    for (i = 1; i <= N; i++)
        C[i].f = lower_bound(X+1, X+h+1, C[i].f) - X,
        C[i].s = lower_bound(X+1, X+h+1, C[i].s) - X;

    sort(C+1, C+N+1, cmp_pair);
    
    for (i = 1; i <= N; i++)
        D[C[i].s] = maxim(D[C[i].s], D[C[i].f-1] + X[C[i].s] - X[C[i].f] + 1);
    for (i = 1; i <= h; i++)
        bst = maxim(bst, D[i]);

    printf("%d\n", bst);

    return 0;
}