Pagini recente » Cod sursa (job #3243639) | Cod sursa (job #1882639) | Cod sursa (job #3144129) | Cod sursa (job #2737379) | Cod sursa (job #139207)
Cod sursa(job #139207)
#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 max3(int a, int b, int c)
{ return maxim(maxim(a, b), c); }
int main(void)
{
int i;
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 <= N; i++)
D[C[i].s] = max3(D[C[i].s], D[C[i].s-1], D[C[i].f-1] + X[C[i].s] - X[C[i].f] + 1);
for (i = 1; i <= h; i++)
bst = maxim(bst, D[i]);
printf("%d\n", bst);
return 0;
}