Pagini recente » Cod sursa (job #1282273) | Cod sursa (job #2587629) | Cod sursa (job #1870612) | Cod sursa (job #1212957) | Cod sursa (job #1206901)
#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;
}