Cod sursa(job #1206404)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 9 iulie 2014 20:34:57
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MaxBAND 2000

struct Band
{
    int left;
    int right;
    int nl;
    int nr;
    int l;
} band;
vector<Band> bands;
int best[MaxBAND];

bool sort_right(Band a, Band b)
{
    return a.right < b.right;
}

bool sort_left(Band a, Band b)
{
    return a.left < b.left;
}

int LowerBound(int Key, int Begin, int End)
{
    int Mid, Min_POZ = MaxBAND;
    while(Begin <= End)
    {
        Mid = (Begin+End)/2;
        if(bands[Mid].nr < Key) Begin = Mid+1;
        if(bands[Mid].nr > Key) End = Mid-1;
        if(bands[Mid].nr == Key)
        {
            Min_POZ = Mid;
            End = Mid-1;
        }
    }
    return Min_POZ;
}

int UpperBound(int Key, int Begin, int End)
{
    int Mid, Max_POZ = 0;
    while(Begin <= End)
    {
        Mid = (Begin+End)/2;
        if(bands[Mid].right > Key) End = Mid-1;
        else
        {
            Max_POZ = Mid;
            Begin = Mid+1;
        }
    }
    return Max_POZ;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    int n, i, val, cpy, j, k;

    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d %d", &band.left, &band.right);
        band.l = band.right - band.left;
        bands.push_back(band);
    }
    sort(bands.begin(), bands.end(), sort_left);
    for(i=0, val=0; i < bands.size(); i++, val++)
    {
        cpy = bands[i].left;
        for(; bands[i].left == cpy; i++) bands[i].nl= val;
        i--;
    }
    sort(bands.begin(), bands.end(), sort_right);
    for(i=0, val=0; i < bands.size(); i++, val++)
    {
        cpy = bands[i].right;
        for(; bands[i].right == cpy; i++) bands[i].nr = val;
        i--;
    }

    //for(i=0; i<bands.size(); i++) printf("%d %d %d\n", bands[i].nl, bands[i].nr, bands[i].l);
    //printf("\n");

    best[0] = bands[0].l;
    int lim = bands[bands.size()-1].nr;
    for(i=1; i<=lim; i++)
    {
        best[i] = best[i-1];
        j = LowerBound(i,0,lim);
        //printf("TEST %d %d\n", i, j);
        for(; j < bands.size() && bands[j].nr == i; j++)
        {
            //printf("COI\n");
            int IND = UpperBound(bands[j].left,0,lim);
            //printf("IN LOOP %d %d %d %d %d\n", i, j, IND, bands[j].left, bands[IND].right);
            best[i] = max(best[i], best[IND] + bands[j].right - bands[j].left);
        }
    }
    printf("%d\n", best[lim]);
    //for(i=0; i<=2000; i++) printf("%d\n", best[i]);
    return 0;
}