Cod sursa(job #182157)

Utilizator stefanrStefan Ruseti stefanr Data 20 aprilie 2008 14:14:15
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream.h>
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct interval
{int a,b;}v[100001];

int n,s[100001],tmax;

int poz(int i,int j)
{int i1[2]={1,0},j1[2]={0,-1},k=0;
 interval aux;
 while(i<j)
  {if(v[i].b>v[j].b)
    {aux=v[i];
     v[i]=v[j];
     v[j]=aux;
     k++;
    }
   i+=i1[k%2];
   j+=j1[k%2];
  }
 return i;
}

void sortare(int i,int j)
{if(i<j)
  {int p=poz(i,j);
   sortare(i,p-1);
   sortare(p+1,j);
  }
}

int cauta(int i,int j,int x)
{if(i>j) return 0;
 int m=(i+j)/2;
 if(v[m].b>x) return cauta(i,m-1,x);
 int ok=cauta(m+1,j,x);
 if(ok>m) return ok;
 return m;
}

int main()
{fin>>n;
int i,p;
for(i=1;i<=n;i++) fin>>v[i].a>>v[i].b;
sortare(1,n);
s[1]=v[1].b-v[1].a;
for(i=2;i<=n;i++)
 {s[i]=s[i-1];
  p=cauta(1,i-1,v[i].a);
  if(s[p]+v[i].b-v[i].a>s[i]) s[i]=s[p]+v[i].b-v[i].a;
 }
fout<<s[n];
fin.close();
fout.close();
return 0;
}