Pagini recente » Cod sursa (job #65001) | Cod sursa (job #1392852) | Cod sursa (job #2165561) | Cod sursa (job #1156461) | Cod sursa (job #2276292)
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int aib[200002];
map<int, int>sorted;
int n;
struct intervale
{
int a, b;
};
intervale v[100002];
bool cmp(intervale a, intervale b)
{
return a.a < b.a;
}
void update(int pos, int val)
{
for(int i = pos; i <= sorted.size(); i += (i & (-i)))
aib[i] = max(aib[i], val);
}
int compute(int pos)
{
int sol = 0;
for(int i = pos; i; i -= (i & (-i)))
sol = max(sol, aib[i]);
return sol;
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i)
f >> v[i].a >> v[i].b, sorted[v[i].a] = 1, sorted[v[i].b] = 1;
sort(v+1, v+n+1, cmp);
map<int, int> ::iterator it;
int ax = 0;
for(it = sorted.begin(); it != sorted.end(); ++it)
{
++ax;
it->second = ax;
}
int ans = 0;
for(int i = 1; i <= n; ++i)
{
int val = compute(sorted[v[i].a]) + (v[i].b - v[i].a);
ans = max(ans, val);
update(sorted[v[i].b], val);
}
g << ans << '\n';
return 0;
}