Cod sursa(job #1710561)

Utilizator GoogalAbabei Daniel Googal Data 29 mai 2016 12:00:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct trupa{long long a,b;}v[100005];
bool comp(trupa x,trupa y)
{
    if(x.b==y.b) return x.a<y.a;
    return x.b<y.b;
}
int i,j,n,m,p,u,nextt4;
long long bestt[100005],maxx;
int main()
{

 fin>>n;
 for(i=1;i<=n;i++) fin>>v[i].a>>v[i].b;
 sort(v+1,v+n+1,comp);
 for(i=1;i<=n;i++)
 {
   if(v[i].a>v[1].b)
   {
       p=1;u=i;nextt4=v[i].a;
       while(p<u)
       {
           m=(p+u)/2;
           if(v[m].b<=nextt4) p=m+1;
           else u=m;
       }
       m=(p+u)/2;
       if(v[m].b>nextt4) m--;
       bestt[i]=max(bestt[m]+v[i].b-v[i].a,maxx);
       if(bestt[i]>maxx) maxx=bestt[i];
   }
   else bestt[i]=max(v[i].b-v[i].a,maxx);
   if(bestt[i]>maxx) maxx=bestt[i];
 }

fout<<bestt[n];

    return 0;
}