Cod sursa(job #1206016)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 8 iulie 2014 18:06:07
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
#define MAX 100005
struct interval
{
    int st, dr;
};
interval v[MAX];

int k[MAX], sol[MAX];
bool comp(interval a, interval b)
{
    if(a.st == b.st)
        return a.dr > b.dr;
    return a.st < b.st;
}
bool comp2(int a, int b)
{
    return a > b;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n, i, R, L;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].st,&v[i].dr);
    sort(v+1,v+n+1,comp);
    int *poz;
    int u=0, el;
    for(i=1; i<=n; i++)
    {
        poz = lower_bound(k+1,k+u+1,v[i].st, comp2);
        el = (int)(poz-k);
        if(el >= u)
            u++;
        k[el] = v[i].dr;
        sol[el] += v[i].dr-v[i].st;
    }
    printf("%d",sol[1]);
    return 0;
}