Pagini recente » Cod sursa (job #410915) | Cod sursa (job #2733645) | Cod sursa (job #2110680) | Cod sursa (job #155398) | Cod sursa (job #249935)
Cod sursa(job #249935)
#include<stdio.h>
long long best[100000],m2,i,t,max,j,k,l,m,n;
struct concert {long long int x,y;} v[100000],norm[100000];
int sort(int i,int j){
concert aux;
int di=1,dj=0,au;
while(i<j)
{if(v[i].y>v[j].y)
{aux=v[i];
v[i]=v[j];
v[j]=aux;
au=di;
di=dj;
dj=au;}
i+=di;
j-=dj;
}
return i;}
void quick(int st,int dr)
{int p;
if(st<dr)
{p=sort(st,dr);
quick(st,p-1);
quick(p+1,dr);
}
}
int caut(int val){
if(val<norm[1].y)return 0;
int p=1,u=i,mij;
while(p<=u)
{mij=(p+u)>>1;
if(norm[mij].y<val)
p=mij+1;
else
if(norm[mij].y>val)
u=mij-1;
else
return mij;
}
return u;
}
int main(){
FILE *f=fopen("heavymetal.in","r");
fscanf(f,"%lld",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lld %lld",&v[i].x,&v[i].y);
fclose(f);
quick(1,n);
for(i=1;i<=n;i++)
if(v[i].y==v[i-1].y)
norm[i]=norm[i-1];
else
{norm[i].x=norm[i-1].x+1;
norm[i].y=v[i].y;}
k=1;
for(i=1;i<=n;i++)
{t=caut(v[i].x);
if(v[i].y!=v[i-1].x)
k++;
if(best[k]==0)
best[k]=best[k-1];
max=best[k];
t=norm[t].x+1;
m2=best[t];
m2+=v[i].y;
m2-=v[i].x;
if(m2>max)
best[k]=m2;
}
FILE *g=fopen("heavymetal.out","w");
fprintf(g,"%lld",best[k]);
fclose(g);
return 0;}