Cod sursa(job #1239757)

Utilizator robertstrecheStreche Robert robertstreche Data 9 octombrie 2014 18:58:59
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <algorithm>

#define lmax 100005

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

long long n,nr,nrr,ma;

long long a[lmax],b[lmax],lung[lmax];

typedef struct el
{
    long long p,u,l;
};
el v[lmax];

inline bool comp(el e1,el e2)
{
    if (e1.u!=e2.u)
     return e1.u<e2.u;

    return e1.p<e2.p;
}

inline long long caut(long long x)
{
    long long s=1,d=nrr;

    while (s<d)
     {
         long long m=(s+d)/2;

         if (b[m]==x)
          return m;

         if (b[m]>x)
          d=m-1;

         else
          s=m+1;
     }

     return s;
}

inline void normalizare()
{
    long long i;

    for (i=1;i<=n;i++)
     {
         el x=v[i];

         v[i].p=caut(x.p);

         v[i].u=caut(x.u);
     }
}

int main()
{
   f>>n;

   for (long long i=1;i<=n;i++)
    {
       f>>v[i].p>>v[i].u;
       v[i].l=v[i].u-v[i].p;

       a[++nr]=v[i].p;
       a[++nr]=v[i].u;
    }

   sort(a+1,a+nr+1);

   for (long long i=1;i<=nr;i++)
    if (a[i]!=a[i-1])

      b[++nrr]=a[i];

     normalizare();

   sort(v+1,v+n+1,comp);

   long long nmax=v[n].u,j=1;

    for (long long i=1;i<=nmax;i++)
     {
         lung[i]=lung[i-1];

         while (v[j].u<i)
          j++;

         while (v[j].u==i)
          {
              if (lung[v[j].u]<lung[v[j].p]+v[j].l)
                lung[v[j].u]=lung[v[j].p]+v[j].l;
                j++;
          }
     }

     g<<lung[nmax];

   f.close();
   g.close();

}