Cod sursa(job #2505600)

Utilizator ionutlazarIonut LZ ionutlazar Data 7 decembrie 2019 08:36:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct interval
{
    int a,b;
    bool operator < (const interval A) const
    {
        return b<A.b;
    }
};

interval t[100003];
interval dp[100003];

int n,k,x,y,p;

int CautBin(int x)
{
    int st, dr , p, mij;
    st=0;
    dr=p=k;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(dp[mij].a<=x)
        {
            p=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    return p;
}

int main()
{
    int i;
    fin>>n;
    for( i=1;i<=n;i++)
        fin>>t[i].a>>t[i].b;
    sort(t+1,t+n+1);

    for(int i=1;i<=n;i++)
    {
        x=t[i].a;
        y=t[i].b;
        /// caut binar cea mai din dr poz p cu dp[p].b<=x
        p=CautBin(x);
        if(dp[k].a==y)
            dp[k].b=max(dp[k].b, dp[p].b + y -x);
        else
        {
            k++;
            dp[k].a=y;
            dp[k].b=max(dp[k-1].b, dp[p].b + y -x);

        }
    }
    fout<<dp[k].b<<" ";
    return 0;
}