Pagini recente » Cod sursa (job #1996978) | Cod sursa (job #1684102) | Cod sursa (job #2765339) | Cod sursa (job #1887550) | Cod sursa (job #1783366)
#include <cstdio>
#include <algorithm>
#define MAXN 100000
int d[MAXN+1], lg, n;
struct aa{
int st, dr;
}v[MAXN+1];
inline int maxim(int a, int b){
return (a > b ? a : b);
}
bool cmp(const aa &a, const aa &b){
if(a.dr == b.dr)
return (a.st < b.st);
return (a.dr < b.dr);
}
inline int best(int val)
{
int pas, ans = 0;
for(pas = lg; pas>=1; pas>>=1)
if(ans + pas <= n && v[ans + pas].dr <= val)
ans += pas;
return ans;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int i, x;
scanf("%d", &n);
lg = 1;
while((lg << 1) <= n)
lg<<=1;
for(i=1; i<=n; ++i)
scanf("%d%d", &v[i].st, &v[i].dr);
std::sort(v+1, v+n+1, cmp);
for(i=1; i<=n; ++i)
{
x = best(v[i].st);
d[i] = maxim(d[i-1], v[i].dr - v[i].st + d[x]);
}
printf("%d", d[n]);
return 0;
}