Pagini recente » Cod sursa (job #461671) | Cod sursa (job #2585836) | Cod sursa (job #404569) | Cod sursa (job #2437397) | Cod sursa (job #1430628)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N;
int a[100002], b[100002], d[100001];
int bs(vector<pair<int, int>>& v, int a, int r) {
int l = 0;
int aux = -1, currentMax = 0;
r--;
while (l <= r) {
int m = (l + r)/2;
if (v[m].second <= a && v[m].second >= currentMax) {
if (currentMax == v[m].second) {
aux = max(aux, m);
} else {
aux = m;
}
currentMax = v[m].second;
}
if (a < v[m].second) {
r = m - 1;
}
else {
l = m + 1;
}
}
return aux + 1;
}
int main()
{
fin >> N;
vector<pair<int, int>> v(N);
int m = 0;
for (int i = 0; i < N; i++) {
int x, y;
fin >> x >> y;
v[i] = make_pair(x, y);
}
sort(v.begin(), v.end(),
[](const pair<int,int>& p1, const pair<int, int>& p2) {
return p1.second < p2.second;
});
d[0] = 0;
d[1] = v[0].second - v[0].first;
for (int i = 2; i <= N; i++) {
d[i] = max(d[i - 1], d[bs(v, v[i - 1].first, i - 1)] + v[i - 1].second - v[i - 1].first);
}
fout << d[N] << endl;
}