Pagini recente » Cod sursa (job #1935964) | Cod sursa (job #38568) | Cod sursa (job #2143385) | Cod sursa (job #1110844) | Cod sursa (job #1853115)
#include<cstdio>
#include<algorithm>
using namespace std;
struct inter{int st,dr;};
struct steve{int v,c;};
inter v[100001];
steve stiv[150001];
bool sor(inter a,inter b)
{
return a.dr<b.dr;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,h=0,mid,poz;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&v[i].st,&v[i].dr);
}
for(i=1;i<=150000;i++)
{
stiv[i].c=1e9+1;
}
sort(v+1,v+n+1,sor);
for(i=1;i<=n;i++)
{
mid=1<<16;
poz=0;
while(mid>0)
{
if(stiv[poz+mid].c<=v[i].st)
{
poz+=mid;
}
mid/=2;
}
if(stiv[poz].v+v[i].dr-v[i].st>stiv[h].v)
{
h++;
stiv[h].v=stiv[poz].v+v[i].dr-v[i].st;
stiv[h].c=v[i].dr;
}
}
printf("%d",stiv[h].v);
return 0;
}