Cod sursa(job #138028)

Utilizator thebest001Neagu Rares Florian thebest001 Data 17 februarie 2008 19:55:08
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <math.h>

int n;long a[1000][2],b[1000][2];

int partitionare(int st,int dr)
{
   int m,i,j;
   long p;
   long aux;
   m=(st+dr)/2;
   p=a[m][1];
   i=st-1;
   j=dr+1;
   while (1)
   {
      do {++i;}while (a[i][1]<p);
      do {--j;}while (a[j][1]>p);
      if (i<j)
      {
         aux=a[i][1];
         a[i][1]=a[j][1];
         a[j][1]=aux;
         aux=a[i][0];
         a[i][0]=a[j][0];
         a[j][0]=aux;
      } else
         return j;
   }
}

void qsort(int st,int dr)
{
   int p;
   if (st<dr)
   {
      p=partitionare(st,dr);
      qsort(st,p);
      qsort(p+1,dr);
   }
}

int main()
{
   freopen("heavymetal.in","r",stdin);
   freopen("heavymetal.out","w",stdout);
   scanf("%d",&n);
   int i;
   for (i=1;i<=n;i++)
   {
      scanf("%ld %ld",&a[i][0],&a[i][1]);
   }
   qsort(1,n);
   int ai,bi,max=0,g=0;
   ai=a[1][0];
   bi=a[1][1];
//   sum=a[1][1]-a[1][0];
   g=0;
   for (i=2;i<=n;i++)
   {
      if (a[i][0]-bi<1)
      {
         bi=a[i][1];
      }
      else
      if (a[i][0]-bi==1)
      {
         bi=a[i][1];
         g++;
      }       else
      {
         if (max<bi-ai-g+1)
         {
            max=bi-ai-g+1;
         }
         ai=a[i][0];
         bi=a[i][1];
         g=0;
      }
   }
   if (max<bi-ai-g+1)
   {
      max=bi-ai-g+1;
   }
   ai=a[i][0];
   bi=a[i][1];
   g=0;
   printf("%d",max);
   return 0;
}