Cod sursa(job #854266)

Utilizator Theorytheo .c Theory Data 13 ianuarie 2013 01:28:36
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<cassert>
#include<cstdio>
#include<algorithm>

#define NMAX 100004
using namespace std;

int N ;
struct interval{ int st, dr;};
interval v[NMAX];

long long d[NMAX];

struct cmp {
    bool operator ()(const interval &a, const interval &b) const{
        return a.dr < b.dr;
    }
};


void Read() {

    assert (freopen("heavymetal.in", "r", stdin));
    assert (scanf("%d" , &N));

    for(int i = 1; i <= N; i++)
        assert (scanf ("%d %d", &v[i].st , &v[i].dr) == 2);
}


int binary_search(int k,int p){
    int step = 1, pos = 0;

    for(step ; step <= p; (step <<= 1));

    for(pos = 0; step ; (step >>= 1))
        if(pos + step <= p && v[pos + step].dr <= k)
            pos += step;
    return pos;
}


void Solve() {

    sort (v + 1, v + 1 + N, cmp());
    d[1] = v[1].dr - v[1].st;

    for(int i = 2; i <= N; i++)
        d[i] = max (d[i - 1], d[binary_search(v[i].st,i)] + v[i].dr - v[i].st);
}


void Print() {

   assert(freopen("heavymetal.out", "w", stdout));
   printf("%d", d[N]);
}


int main(){

    Read ();

    Solve ();

    Print ();

    return 0;
}