Pagini recente » Cod sursa (job #1826643) | Cod sursa (job #2160900) | Cod sursa (job #1040461) | Cod sursa (job #402268) | Cod sursa (job #134758)
Cod sursa(job #134758)
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
const int Nmax = 100005;
int N;
pair<int, int> T[Nmax];
vector<int> v;
int Best[2*Nmax];
void ReadData() {
assert(scanf("%d", &N) == 1);
assert(1 <= N && N <= 100000);
for (int i = 0; i < N; ++i) {
assert(scanf("%d %d", &T[i].first, &T[i].second) == 2);
assert(1 <= T[i].first && T[i].first <= 1000000000);
assert(1 <= T[i].second && T[i].second <= 1000000000);
}
}
void Normalizeaza() {
for (int i = 0; i < N; ++i) {
v.push_back(T[i].first);
v.push_back(T[i].second);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 0; i < N; ++i) {
T[i].first = lower_bound(v.begin(), v.end(), T[i].first) - v.begin();
T[i].second = lower_bound(v.begin(), v.end(), T[i].second) - v.begin();
}
}
void Solve() {
Normalizeaza();
sort(T, T+N);
Best[T[0].second] = v[T[0].second] - v[T[0].first];
for (int i = 1; i < N; ++i) {
for (int j = T[i-1].first+1; j <= T[i].first; ++j)
Best[j] = max(Best[j], Best[j-1]);
Best[T[i].second] = max(Best[T[i].second], Best[T[i].first] + v[T[i].second] - v[T[i].first]);
}
for (int i = T[N-1].first+1; i < int(v.size()); ++i)
Best[i] = max(Best[i], Best[i-1]);
printf("%d\n", Best[int(v.size())-1]);
}
int main() {
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
ReadData();
Solve();
}