Cod sursa(job #1866662)

Utilizator UrsuDanUrsu Dan UrsuDan Data 3 februarie 2017 13:44:48
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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=(left+right)/2;
    ok=0;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(d[mid].cpt>x)
        {
            ok=1;
            right=mid-1;
        }
        else
        {
            ok=0;
            left=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=2; i<=n+1; i++)
        scanf("%d%d",&v[i].left,&v[i].right);
    sort(v+2,v+n+2,cmp);
    for(i=2; i<=n+1; i++)
    {
        if(v[i].left<d[i-1].cpt)
        {
        x=v[i].left;
        t=caut(1,i-1);
        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+1].val);
    return 0;
}