Cod sursa(job #1866688)

Utilizator UrsuDanUrsu Dan UrsuDan Data 3 februarie 2017 14:03:28
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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 main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,t,mid,left,right;
    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;
            ok=0;
            left=0;
            right=i-2;
            while(left<=right)
            {
                mid=(left+right)/2;
                if(d[mid].cpt<=x)
                {
                    ok=0;
                    left=mid+1;
                }
                else
                {
                    ok=1;
                    right=mid-1;
                }
            }
            t=mid;
            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;
}