Cod sursa(job #189098)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 12 mai 2008 09:20:24
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream.h>
int a,b,min,max,i,j,n,k;
long long sol=0;
struct sir {int x,y;};
sir v[1000010],aux;

void pozitie(int li, int ls, int &k)

  { int i,j,di=1,dj=0,aux2;

    i=li; j=ls;
     while(i<j)

      { if(v[i].x>v[j].x||v[i].x==v[j].x&&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;

 quick(1,n);


min=v[1].x; max=v[1].y; sol=max-min;

for(i=2;i<=n;i++)

  { a=v[i].x; b=v[i].y;

      if(a>=max) { sol+=(b-a); max=b; }
  }

g<<sol;

f.close();
g.close();
return 0;
}