Pagini recente » Cod sursa (job #1625650) | Cod sursa (job #1887046) | Cod sursa (job #1615948) | Cod sursa (job #1691284) | Cod sursa (job #2051007)
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
#define maxim(a, b) ((a > b) ? a : b)
#define PII pair<int, int>
#define f first
#define s second
#define NMax 100005
int N, X[NMax<<1], D[NMax<<1], h, bst;
PII C[NMax];
set<int> A;
int cmp_pair(const PII& a, const PII& b)
{ return a.s < b.s; }
int main(void)
{
int i, j = 1;
set<int>::iterator it;
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
{
scanf("%d %d", &C[i].f, &C[i].s);
C[i].s--;
A.insert(C[i].f);
A.insert(C[i].s);
}
for (it = A.begin(); it != A.end(); ++it)
X[++h] = *it;
for (i = 1; i <= N; i++)
C[i].f = lower_bound(X+1, X+h+1, C[i].f) - X,
C[i].s = lower_bound(X+1, X+h+1, C[i].s) - X;
sort(C+1, C+N+1, cmp_pair);
for (i = 1; i <= h; i++)
{
D[i] = D[i-1];
for (; j <= N && C[j].s == i; ++j)
D[i] = maxim(D[i], D[C[j].f-1] + X[C[j].s] - X[C[j].f] + 1);
}
printf("%d\n", D[h]);
return 0;
}