Pagini recente » Cod sursa (job #2640917) | Cod sursa (job #1732730) | Cod sursa (job #2583207) | Cod sursa (job #493958) | Cod sursa (job #2172178)
#include<cstdio>
#include<algorithm>
using namespace std;
int aib[200005];
struct coord{
int nr,poz,tip;
}v[200005];
struct format{
int x,y,l;
}f[100005];
int cmp(coord a,coord b){
return a.nr<b.nr;}
int cmp2(format a,format b){
return a.y<b.y;}
int update(int poz,int nr){
int i;
for(i=poz;i<=200000;i=i+(i&(-i)))
aib[i]=max(aib[i],nr);}
int query(int poz){
int sol=0,i;
for(i=poz;i>0;i=i-(i&(-i)))
sol=max(sol,aib[i]);
return sol;}
int main(){
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,num=0,sol;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&f[i].x,&f[i].y),f[i].l=f[i].y-f[i].x,v[++num].nr=f[i].x,v[num].poz=i,v[num].tip=0,v[++num].nr=f[i].y,v[num].poz=i,v[num].tip=1;
sort(v+1,v+num+1,cmp);
int u=0;
for(i=1;i<=num;i++){
if (v[i].nr!=v[i-1].nr)
u++;
if (v[i].tip==0)
f[v[i].poz].x=u;
else
f[v[i].poz].y=u;}
sort(f+1,f+n+1,cmp2);
for(i=1;i<=n;i++){
sol=f[i].l+query(f[i].x);
update(f[i].y,sol);}
printf("%d\n",query(200000));
return 0;}