Cod sursa(job #1852369)

Utilizator andy1207Cioltan Andrei andy1207 Data 20 ianuarie 2017 19:01:57
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<cstdio>
#include<algorithm>
#include<vector>

const int Nmax=100000;

struct interv
{
 int x,y,rez;
};
interv v[Nmax+1];

bool comparare(interv a,interv b)
{
 if(a.y<b.y)
    return true;
 if(a.y>b.y)
    return false;
 if(a.x<b.x)
    return true;
 return false;
}
int main()
{
 int n;
 freopen("heavymetal.in","r",stdin);
 freopen("heavymetal.out","w",stdout);
 scanf("%d ",&n);
 for(int i=1;i<=n;i++)
     scanf("%d %d ",&v[i].x,&v[i].y);
 std::sort(v+1,v+n+1,comparare);
 for(int i=1;i<=n;i++)
    {
     int st=1,dr=i-1,sol=0;
     while(st<=dr)
          {
           int mij=(st+dr)/2;
           if(v[mij].y<=v[i].x)
              {
               sol=mij;
               st=mij+1;
              }
           else
               dr=mij-1;
          }
     v[i].rez=std::max(v[i-1].rez, v[i].y-v[i].x+v[sol].rez);
    }
 printf("%d\n",v[n].rez);
return 0;
}