Pagini recente » Cod sursa (job #1883697) | Cod sursa (job #2707996) | Cod sursa (job #2988696) | Cod sursa (job #3005394) | Cod sursa (job #1783188)
#include <fstream>
#include <cstdio>
#include <algorithm>
#define VAL 100005
using namespace std;
struct interval
{
int l;
int r;
};
interval v[VAL];
int N, i, mx;
int best[VAL];
bool cmp(interval a, interval b)
{
return a.r<b.r;
}
int cautbin()
{
int be=1;
int en=i;
int ans=0;
int mid;
while (be<=en)
{
mid=(be+en) / 2;
if (v[mid].r<v[i].l)
{
ans=mid;
be=mid+1;
}
else
en=mid-1;
}
return ans;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &N);
for (i=1; i<=N; i++)
scanf("%d %d", &v[i].l, &v[i].r);
sort(v+1, v+N+1, cmp);
for (i=1; i<=N; i++)
{
v[i].r--;
best[i]=best[cautbin()]+v[i].r-v[i].l+1;
mx=max(mx, best[i]);
}
printf("%d\n", mx);
return 0;
}