Cod sursa(job #1223050)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 25 august 2014 12:24:55
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 100003;

struct band {

    int left, right;

};

bool operator < (const band &a, const band &b) {

    if (a.right < b.right)
        return 1;
    if (a.right == b.right)
        return a.left < b.left;
    return 0;

}

band V[NMAX];
int sel[NMAX], D[NMAX];

int binarySearch (int right, const int &val) {

    int left = 1, middle;
    while (left < right) {
        middle = left + right >> 1;
        if (V[sel[middle]].right <= val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;

}

int main () {

    freopen ("heavymetal.in", "r", stdin);
    freopen ("heavymetal.out", "w", stdout);
    int N, i, j, k;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%d%d", &V[i].left, &V[i].right);
    sort (V + 1, V + N + 1);
    sel[1] = 1;
    D[1] = V[1].right - V[1].left;
    for (i = j = 2; i <= N; ++i, ++j) {
        if (V[sel[j - 1]].right <= V[i].left) {
            sel[j] = i;
            D[j] = D[j - 1] + V[i].right - V[i].left;
        }
        else {
            k = binarySearch (j - 1, V[i].left);
            if (D[j - 1] - D[k - 1] < V[i].right - V[i].left) {
                j = k;
                D[j] = D[j - 1] + V[i].right - V[i].left;
                sel[j] = i;
            }
        }
    }
    printf ("%d", D[j - 1]);

}