Cod sursa(job #184783)

Utilizator firewizardLucian Dobre firewizard Data 24 aprilie 2008 12:14:27
Problema Heavy metal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>
#define max(a,b)((a>b)?a:b)
#define FOR(i,s,d) for(i=(s);i<=(d);++i)
long a[100005],b[100005],n,i,j,v[1000001],ind[1000001],q;

int comp(const void * n1 ,const void * n2){
    return b[*((long*)n1)]-b[*((long*)n2)];
}

int bs(long,long,long);
int bs2(long,long,long);

int main ()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%ld",&n);
    FOR (i,1,n){
        scanf("%ld %ld",&a[i],&b[i]);
        ind[i]=i;
        }
    qsort(ind+1,n,sizeof(long),comp);

    FOR (i,1,n){
        if (v[a[ind[i]]]==0)
        if(i!=1)
           FOR (j,1,i)
               if (a[ind[i]]<=b[ind[j]]){
                  v[a[ind[i]]]=v[b[ind[j-1]]];
                  break;
                  }
        //v[a[ind[i]]]=v[b[ind[(bs2(2,i,a[ind[i]]))]]];
        v[b[ind[i]]]=v[b[ind[i-1]]];
        q=bs(1,i+1,b[ind[i]]);
        if(q!=0)v[b[ind[i]]]=max(v[b[ind[i]]],v[a[ind[q]]]+b[ind[q]]-a[ind[q]]);
        }
    printf("%ld",v[b[ind[n]]]);
    //printf("\n");
    //FOR (i,1,b[ind[n]])printf("%ld ",v[i]);
    return 0;   
}

int bs(long s,long d,long v)
{
    
  while (s<d)   
  {
      long mid=(s+d)/2;
      if(b[ind[mid]]==v)return mid;
      if(b[ind[mid]]<v)
      s=mid+1;
      else d=mid;
      }
  if(b[ind[s]]==v)return s;
  return 0;
}
int bs2(long s,long d,long v)
{
    
  while (s<d)   
  {
      long mid=(s+d)/2;
      if(b[ind[mid]]==v)return mid;
      if(b[ind[mid]]<v)
      s=mid+1;
      else d=mid;
      }
  return s;
}