Pagini recente » Cod sursa (job #693533) | Cod sursa (job #2699731) | Cod sursa (job #2532922) | Cod sursa (job #3219625) | Cod sursa (job #340534)
Cod sursa(job #340534)
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int NMAX=100005;
int N,VMAX;
struct I
{
int A,B;
int nA,nB;
} v[NMAX];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
map<int,int> F;
int cmp(I X,I Y) {return X.B<Y.B;}
long long a[2*NMAX],sol;
inline int LSB(int x) { return x&-x; }
long long query(int p)
{
long long Max=0;
for (;p>0;p-=LSB(p)) Max=max(Max,a[p]);
return Max;
}
void update(int p,long long x)
{
for (;p<=VMAX;p+=LSB(p)) a[p]=max(a[p],x);
}
int main()
{
int i,x,y;
f>>N;
for (i=1;i<=N;++i)
{
f>>x>>y;
F[x]=1;
F[y]=1;
v[i].A=x;v[i].B=y;
}
map<int,int>::iterator it;
for (i=1,it=F.begin();it!=F.end();++it,++i)
it->second=i;
for (i=1;i<=N;++i)
v[i].nA=F[v[i].A],v[i].nB=F[v[i].B];
sort(v+1,v+N+1,cmp);
VMAX=v[N].nB;
for (i=1;i<=N;++i)
{
long long t=query(v[i].nA)+v[i].B-v[i].A;
sol=max(sol,t);
update(v[i].nB,t);
}
g<<sol;
return 0;
}