Cod sursa(job #223333)

Utilizator Mishu91Andrei Misarca Mishu91 Data 28 noiembrie 2008 11:03:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

#define MAX_N 100005
#define DIM 8192

int N, logN;
long Bst[MAX_N];
int pz = DIM-1;
char buf[DIM];
struct met{long long li, lf;} V[MAX_N];

void read(long long &x)
{
    x = 0;
    while(!isdigit(buf[pz]))
        if(++pz == DIM)
            fread(buf, sizeof (char), DIM, stdin), pz = 0;
    while(isdigit(buf[pz]))
    {
        x = x*10 + (buf[pz] - '0');
        if(++pz == DIM)
            fread(buf, sizeof (char), DIM, stdin), pz = 0;
    }
}

void citire()
{
    long long x;
    read(x);
    N = x;

    for(int i = 1; i <= N; ++i)
    {
        read(V[i].li); read(V[i].lf);
    }
}

struct cmp
{
    bool operator()(const met a, const met b) const
    {
        return ((a.lf < b.lf) || (a.lf == b.lf) && (a.li < b.li));
    }
};

long b_search(long x)
{
    int i, lg;
    for(i = 0, lg = logN; lg; lg >>= 1)
        if(i + lg <= N && V[i + lg].lf <= x)
            i += lg;
    return i;
}

void solve()
{
    sort(V+1, V+N+1, cmp());

   for(logN = 1; logN <= N; logN <<= 1);

    for(int i = 1; i <= N; ++i)
    {
        Bst[i] = Bst[i-1];
        long poz = b_search(V[i].li);
        long dif = V[i].lf - V[i].li;
        if(Bst[poz] +  dif> Bst[i])
            Bst[i] =  dif + Bst[poz];
    }
    printf("%ld\n",Bst[N]);
}

int main()
{
    freopen("heavymetal.in","rt",stdin);
    freopen("heavymetal.out","wt",stdout);

    citire();
    solve();
}