Pagini recente » Cod sursa (job #261342) | Cod sursa (job #2705891) | Cod sursa (job #59726) | Cod sursa (job #2454170) | Cod sursa (job #1678405)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
class AIB
{
vector<int> _container;
int leftIndex(int i)
{
return (i ^ (i - 1)) & i;
}
public:
AIB(int size)
{
_container.resize(size + 1, 0);
}
void Add(int index, int value)
{
for (int i = index; i < _container.size(); i += leftIndex(i))
{
_container[i] = max(_container[i], value);
}
}
int Query(int index)
{
int mx = 0;
for (int i = index; i > 0; i -= leftIndex(i))
{
mx = max(mx, _container[i]);
}
return mx;
}
};
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
ios_base::sync_with_stdio(false);
int n, i, a, b, maxEnd = 0;
vector<pair<int, int>> v;
vector<int> best;
f >> n;
for (i = 1; i <= n; i++)
{
f >> a >> b;
v.push_back(make_pair(a, b));
maxEnd = max(maxEnd, b);
}
sort(v.begin(), v.end(), cmp);
best.resize(n);
AIB aib(maxEnd);
for (i = 0; i < v.size(); i++)
{
best[i] = aib.Query(v[i].first) + (v[i].second - v[i].first);
aib.Add(v[i].second, best[i]);
}
int ans = best[0];
for (i = 1; i < n; i++)
{
ans = max(best[i], ans);
}
g << ans;
return 0;
}