Cod sursa(job #249935)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 ianuarie 2009 17:19:07
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#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;}