Pagini recente » Cod sursa (job #2878788) | Cod sursa (job #677709) | Cod sursa (job #2717678) | Cod sursa (job #481362) | Cod sursa (job #2647122)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
typedef long long ll;
typedef pair<int, int> peir;
#define x first
#define y second
const int NMAX = 100002;
vector<peir> v(NMAX);
vector<int> mx(NMAX), D(NMAX);
inline bool comp(peir a, peir b)
{
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(0);
int n;
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v.begin() + 1, v.begin() + n + 1, comp);
for (int i = 1; i <= n; ++i)
{
int s = 1, d = i- 1, mj, rez = 0;
while (s <= d)
{
mj = s + (d - s) / 2;
if (v[i].x >= v[mj].y)
rez = mj, s = mj + 1;
else d = mj - 1;
}
D[i] = v[i].y - v[i].x + mx[rez], mx[i] = max(mx[i - 1], D[i]);
}
int rez = 0;
for (int i = 1; i <= n; ++i) rez = max(rez, mx[i]);
fout << rez;
return 0;
}