Cod sursa(job #668933)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 25 ianuarie 2012 21:04:56
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <algorithm>
#define LE 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
long long  POZ,n,i,TE;
struct two
{
 long long  x,y;
} T[LE],TMAX[LE];
int cmp(two a,two b)
{
  return a.y<b.y;
}
long long  caut(int val)
{
long long  STEP=1,I=0;
  for(; STEP<=POZ; STEP*=2);
  for(; STEP; STEP/=2)
    if (TMAX[I+STEP].y<=val&&I+STEP<POZ) I+=STEP;
  return TMAX[I].x;
}

int main()
{
  f>>n;
  for(i=1; i<=n; i++) f>>T[i].x>>T[i].y;
  sort(T+1,T+n+1,cmp);

  for(i=1; i<=n; i++)
    {
      if (T[i-1].y!=T[i].y)
        {
          POZ++;
          TMAX[POZ].y=T[i].y;
        }
      TMAX[POZ].x=max(TMAX[POZ].x,caut(T[i].x)+(T[i].y-T[i].x));
      TE=max(TMAX[POZ].x,TE);
    }
g<<TE<<'\n';
  f.close();
  g.close();
  return 0;
}