Pagini recente » Cod sursa (job #1008581) | Cod sursa (job #2949430) | Cod sursa (job #1535907) | Cod sursa (job #1813035) | Cod sursa (job #2323176)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <iomanip>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector< pair<long long, long long> > v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
v[i].second--;
}
sort(v.begin(), v.end(), [](const pair<long long, long long>& a, const pair<long long, long long>& b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
});
vector<long long> dp(n);
vector<long long> a(n);
for (int i = 0; i < n; i++) {
a[i] = v[i].second;
}
for (int i = 0; i < n; i++) {
auto it = lower_bound(a.begin(), a.end(), v[i].first);
dp[i] = v[i].second - v[i].first + 1;
if (it != a.begin()) {
dp[i] += dp[prev(it) - a.begin()];
}
if (i > 0) {
dp[i] = max(dp[i], dp[i - 1]);
}
}
cout << dp[n - 1] << '\n';
return 0;
}