Pagini recente » Cod sursa (job #215434) | Cod sursa (job #3032848) | Cod sursa (job #1748515) | Cod sursa (job #2412664) | Cod sursa (job #2104439)
#include <bits/stdc++.h>
#define st first
#define dr second
using namespace std;
pair <int,int> v[100001];
int tmax[100001];
int bs(int k,int x)
{
int rez,pas;
pas=1<<17;
rez=0;
while(pas)
{
if(rez+pas<k && v[rez+pas].dr<=x)
rez+=pas;
pas/=2;
}
return rez;
}
int main()
{
int i,n,pos;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d%d",&v[i].st,&v[i].dr);
sort(v+1,v+n+1,[](pair<int,int> a,pair<int,int> b){return a.dr<b.dr;});
for(i=1; i<=n; i++)
{
pos=bs(i,v[i].st);
tmax[i]=max(tmax[i-1],tmax[pos]+v[i].dr-v[i].st);
}
printf("%d\n",tmax[n]);
return 0;
}