Cod sursa(job #138506)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 18 februarie 2008 18:59:58
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
long int n,i,j,k,a[100002],b[100002],aux,ii,aa,bb,max;
void sh(long int i1,long int i2);
void hd(long int ic,long int nc);
int main()
{
	FILE *f,*g;f=fopen("heavymetal.in","r");g=fopen("heavymetal.out","w");
	fscanf(f,"%ld",&n);for(i=1;i<=n;i++)fscanf(f,"%ld%ld",&a[i],&b[i]);
	for(i=n/2;i>=1;i--)hd(i,n);
	for(i=n;i>=1;i--){sh(1,i);hd(1,i-1);}
	ii=0;
	for(i=1;i<=n;i++)
	{ if(a[i]>a[i-1]){ii++;a[ii]=a[i];b[ii]=b[i];}
	  else
	   if(b[i]>b[ii])b[ii]=b[i];
	}
	aa=a[1];bb=b[1];n=ii;
	for(i=1;i<=n;i++)
	 { if(a[i]<=bb)
	     {if(b[i]>=bb)bb=b[i];}
	   else
	    {max+=(bb-aa);aa=a[i];bb=b[i];}
	 }
	max+=bb-aa;
	fprintf(g,"%ld\n",max);
	fcloseall();
	return 0;
}
void sh(long int i1,long int i2)
{
	aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
void hd(long int ic,long int nc)
{
	long int is,is1;
	is=2*ic;is1=ic+1;
	if(is>nc)return;
	if(is<nc)if(a[is1]>a[is])is=is1;
	if(a[is]>a[ic]){sh(is,ic);hd(is,nc);}
}