Pagini recente » Cod sursa (job #231263) | Cod sursa (job #1077634) | Cod sursa (job #309648) | Cod sursa (job #677812) | Cod sursa (job #2970699)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
pair <int, int> v[100001];
map <int, int> M;
map <int, int>::iterator it;
int n;
bool comp(pair <int, int> a, pair <int, int> b)
{
if (a.second < b.second)
return true;
else if (a.second == b.second)
return a.first < b.first;
return false;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1, comp);
int i = 1;
while (i <= n)
{
int c = v[i].second;
int maxi = 0;
while (i <= n && v[i].second == c)
{
it = M.lower_bound(v[i].first);
if (M.size() == 0 || it == M.begin())
maxi = max(maxi, v[i].second - v[i].first);
else if (it == M.end() || it->first != v[i].first)
it--, maxi = max(maxi, it->second + v[i].second - v[i].first);
else
maxi = max(maxi, it->second + v[i].second - v[i].first);
i++;
}
it = M.end();
if (M.size())
{
it--;
M[c] = max(maxi, it->second);
}
else
M[c] = maxi;
}
it = M.end();
it--;
fout << it->second;
return 0;
}