Cod sursa(job #1860323)

Utilizator MarcSpataruMarc Spataru MarcSpataru Data 27 ianuarie 2017 23:05:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct heavymetal
{
    int st,dr,timp;
};
heavymetal v[100001],f[100001];
bool sortare(heavymetal a, heavymetal b)
{
    return a.dr<b.dr;
}
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,pp;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].st,&v[i].dr);
        v[i].timp=v[i].dr-v[i].st;
    }
    sort(v+1,v+n+1,sortare);
    f[1].st=v[1].st;
    f[1].dr=v[1].dr;
    f[1].timp=v[1].timp;
    int l1,l2,mij;
    for(i=2;i<=n;i++)
    {
        if(v[i].st<f[i-1].dr)
        {
            l1=0;
            l2=i-2;
            pp=0;
            while(l1<=l2)
            {
                mij=(l1+l2)/2;
                if(f[mij].dr<=v[i].st)
                {
                    l1=mij+1;
                    pp=0;
                }
                if(f[mij].dr>v[i].st)
                {
                    l2=mij-1;
                    pp=1;
                }
            }
            if(pp==1)
                mij--;
            if(f[mij].timp+v[i].timp>f[i-1].timp)
            {
                f[i].st=f[i-1].st;
                f[i].dr=v[i].dr;
                f[i].timp=f[mij].timp+v[i].timp;
            }
            else if(f[mij].timp+v[i].timp<=f[i-1].timp)
            {
                f[i].st=f[i-1].st;
                f[i].dr=f[i-1].dr;
                f[i].timp=f[i-1].timp;
            }
        }
        else
        if(v[i].st>=f[i-1].dr)
        {
            f[i].st=f[i-1].st;
            f[i].dr=v[i].dr;
            f[i].timp=f[i-1].timp+v[i].timp;
        }
    }
    printf("%d",f[n].timp);
    return 0;
}