Pagini recente » Cod sursa (job #38390) | Cod sursa (job #1253634) | Cod sursa (job #2891315) | Cod sursa (job #798401) | Cod sursa (job #3295454)
#include <bits/stdc++.h>
using namespace std;
struct interval {
int st, dr;
} v[100001];
bool comp(interval a, interval b) {
return a.dr < b.dr;
}
int n;
unordered_map<int, int> dp;
int binSearch(int k, int limit) {
int res = 0;
for (int step = (1 << 20); step != 0; step >>= 1) {
if (res + step <= limit && v[res + step].dr <= k) {
res += step;
}
}
return v[res].dr;
}
int main() {
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i].st >> v[i].dr;
}
sort(v + 1, v + n + 1, comp);
dp[v[1].dr] = v[1].dr - v[1].st;
for (int i = 2; i <= n; ++i) {
int aux = binSearch(v[i].st, i - 1);
if (dp[aux] + v[i].dr - v[i].st > dp[v[i].dr]) {
dp[v[i].dr] = dp[aux] + v[i].dr - v[i].st;
}
}
cout << dp[v[n].dr];
}