Pagini recente » Cod sursa (job #1810500) | Cod sursa (job #3205716) | Cod sursa (job #2805062) | rar43 | Cod sursa (job #1984291)
#include <iostream>
#include <fstream>
#include <algorithm>
#define maxn 100000
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct miau{long long st,dr;} v[maxn+5];
long long n,i,j,d[maxn+5],poz,maxi;
bool cmp(miau a, miau b)
{
return a.dr<b.dr;
}
int cautbin(int val,int i)
{
int ans=0,pas=1<<20;
while(pas)
{
if(ans+pas<i && v[ans+pas].dr<val) ans+=pas;
pas/=2;
}
return ans;
}
int main()
{
f>>n;
for(i=1;i<=n;i++) f>>v[i].st>>v[i].dr;
sort(v+1,v+n+1,cmp);
d[1]=v[1].dr-v[1].st+1;
for(i=2;i<=n;i++)
{
poz=cautbin(v[i].st,i);
d[i]=v[i].dr-v[i].st+1+d[poz];
d[i]=max(d[i],d[i-1]);
}
maxi=0;
for(i=1;i<=n;i++) if(d[i]>maxi) maxi=d[i];
g<<maxi<<'\n';
return 0;
}