Cod sursa(job #1866681)

Utilizator UrsuDanUrsu Dan UrsuDan Data 3 februarie 2017 13:57:32
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct interval
{
    int left,right;
};
interval v[100010];

struct dinamica
{
    int cpt,val;
};
dinamica d[100010];

int x,ok;

bool cmp(interval x,interval y)
{
    if(x.left==y.left)
        return x.right<y.right;
    else
        return x.left<y.left;
}

int caut(int left,int right)
{
    int mid;
    ok=0;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(d[mid].cpt<=x)
        {
            ok=0;
            left=mid+1;
        }
        else
        {
            ok=1;
            right=mid-1;
        }
    }
    return mid;
}

int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,t;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].left,&v[i].right);
    sort(v+1,v+n+1,cmp);
    d[1].cpt=v[1].right;
    d[1].val=v[1].right-v[1].left;
    for(i=2; i<=n; i++)
    {
        if(v[i].left<d[i-1].cpt)
        {
            x=v[i].left;
            t=caut(0,i-2);
            if(ok==1)
                t--;
            if(d[t].val+v[i].right-v[i].left>d[i-1].val)
            {
                d[i].val=d[t].val+v[i].right-v[i].left;
                d[i].cpt=v[i].right;
            }
            else
            {
                d[i].val=d[i-1].val;
                d[i].cpt=d[i-1].cpt;
            }
        }
        else
        {
            d[i].cpt=v[i].right;
            d[i].val=d[i-1].val+v[i].right-v[i].left;
        }
    }
    printf("%d",d[n].val);
    return 0;
}