Pagini recente » Cod sursa (job #1944658) | Cod sursa (job #2691329) | Cod sursa (job #3129369) | Cod sursa (job #1264040) | Cod sursa (job #1851113)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
const int Nmax = 100000;
int n;
struct segment
{
int a,b;
segment(): a(0),b(0) {}
};
unordered_map<int,int> H;
vector<segment> segm;
set<int> s;
int aint[Nmax*4+5];
void update(int p,int val)
{
p += n;
aint[p] = max(val,aint[p]);
for (; p > 1; p >>= 1)
aint[p>>1] = max(aint[p],aint[p^1]);
}
int query(int l,int r)
{
int ret = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if (l&1)
{
ret = max(ret,aint[l]);
l++;
}
if (r & 1)
{
r--;
ret = max(ret,aint[r]);
}
}
return ret;
}
bool comp(const segment &A,const segment &B)
{
if (A.a == B.a)
return A.b < B.b;
return A.a < B.a;
}
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin >> n;
segm = vector<segment>(n+1);
for (int i = 1; i <= n; i++)
{
fin >> segm[i].a >> segm[i].b;
s.insert(segm[i].a);
s.insert(segm[i].b);
}
int m = 0;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
H[*it] = ++m;
sort(segm.begin()+1,segm.end(),comp);
int best = 0;
for (int i = 1; i <= n; i++)
{
int R = H[segm[i].a];
int ans = query(0,R-1);
ans += segm[i].b - segm[i].a;
update(H[segm[i].b]-1,ans);
best = max(best,ans);
}
fout << best;
}