Cod sursa(job #854264)

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

#include<algorithm>

#define NMAX 100004
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

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() {
   fin >>N;
    for(int i = 1; i <= N; i++)
        fin >>v[i].st >> v[i].dr;
}


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() {
    fout << d[N];
}
int main(){

    Read ();

    Solve ();

    Print ();


    return 0;
}