Pagini recente » Cod sursa (job #1284894) | Cod sursa (job #205771) | Cod sursa (job #2468436) | Cod sursa (job #1352771) | Cod sursa (job #340542)
Cod sursa(job #340542)
#include <fstream>
#include <algorithm>
#include <vector>
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");
int cmpA(I X,I Y) {return X.A<Y.A;}
int cmpB(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);
}
vector<int> x;
#define pb push_back
int main()
{
int i;
f>>N;
for (i=1;i<=N;++i)
{
f>>v[i].A>>v[i].B;
x.pb(v[i].A);
x.pb(v[i].B);
}
sort(x.begin(),x.end());
unique(x.begin(),x.end());
sort(v+1,v+N+1,cmpA);
size_t j;
for (i=1,j=0;i<=N;++i)
{
for (;x[j]<v[i].A;++j);
v[i].nA=j+1;
}
sort(v+1,v+N+1,cmpB);
for (i=1,j=0;i<=N;++i)
{
for (;x[j]<v[i].B;++j);
v[i].nB=j+1;
}
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;
}