Pagini recente » Cod sursa (job #1860885) | Cod sursa (job #784039) | Cod sursa (job #777912) | Cod sursa (job #1219913) | Cod sursa (job #189809)
Cod sursa(job #189809)
#include<fstream.h>
int car[100000],s,best[100000],ora[100000],max0=0,max,maxf=0,p,k,i,j=1,n;
struct sir {int x,y;};
sir v[100000],aux;
void pozitie(int li, int ls, int &k)
{ int i,j,di=0,dj=1,aux2;
i=li; j=ls;
while(i<j)
{ if(v[i].y>v[j].y) { aux=v[i]; v[i]=v[j]; v[j]=aux;
aux2=di; di=dj; dj=aux2;}
i+=di; j-=dj;
}
k=i;
}
void quick ( int li, int ls)
{ if(li<ls) {pozitie (li,ls,k);
quick(li,k-1);
quick(k+1,ls);
}
}
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++)
{f>>v[i].x>>v[i].y;
car[v[i].y]=1;
if(v[i].y>max0) max0=v[i].y;
}
quick(1,n); k=0;
for(i=1;i<=max0;i++)
if(car[i])
{ ora[++k]=i; p=k; max=0;
while(v[j].y==i)
{{ while(v[j].x<ora[--p]) ;
s=v[j].y-v[j].x+best[p];
if(s>max) max=s;
}
j++;
}
best[j-1]=max;
if(best[j-1] >maxf) maxf=best[j-1];
}
g<<maxf;
f.close();
g.close();
return 0;
}