Cod sursa(job #1206901)

Utilizator ZenusTudor Costin Razvan Zenus Data 11 iulie 2014 14:31:52
Problema Heavy metal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

#define NMAX 100005

set < pair < int , int > > S;
set < pair < int , int > > :: iterator it;
pair < int , pair < int , int > > C[NMAX];
int i,N,precedent,left,right,cost;
int Best[NMAX];

int binary_search(int X)
{
    int left=1,right=N,mid;

    while (left<=right)
    {
        mid=(left+right)>>1;

        if (C[mid].first==X)
        return mid;

        (C[mid].first<X) ? left=mid+1 : right=mid-1;
    }
}

int binary_search2(int X)
{
    int left=1,right=N,mid,final=0;

    while (left<=right)
    {
        mid=(left+right)>>1;

        if ((C[mid].second.second)<=X)
        {
            final=mid;
            left=mid+1;
            continue;
        }

        right=mid-1;
    }

    return final;
}

int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);

scanf("%d",&N);

for (i=1;i<=N;++i)
{
    scanf("%d%d",&(C[i].second).first,&(C[i].second).second);

    S.insert(make_pair((C[i].second).second,i));
}

for (it=S.begin(),i=1;it!=S.end();++it,++i)
{
    if (precedent==(*it).second) ++i;
    C[(*it).second].first=i;

    precedent=(*it).second;
}

sort(C+1,C+N+1);

for (i=1;i<=N;++i)
{
    Best[i]=Best[i-1];

    left=binary_search(i);
    right=left;

    while (C[left].first==i)
    {
        cost=Best[binary_search2((C[left].second).first)];

        Best[i]=max(Best[i],cost+(C[left].second).second-(C[left].second).first);
        --left;
    }

    while (C[right].first==i)
    {
        cost=Best[binary_search2((C[right].second).first)];

        Best[i]=max(Best[i],cost+(C[right].second).second-(C[right].second).first);
        ++right;
    }
}

printf("%d\n",Best[N]);

return 0;
}