Cod sursa(job #340534)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 15 august 2009 11:36:31
Problema Heavy metal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int NMAX=100005;
int N,VMAX;
struct I
{
    int A,B;
    int nA,nB;
} v[NMAX];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
map<int,int> F;
int cmp(I X,I Y) {return X.B<Y.B;}
long long a[2*NMAX],sol;
inline int LSB(int x) { return x&-x; }
long long query(int p)
{
     long long Max=0;
     for (;p>0;p-=LSB(p)) Max=max(Max,a[p]);
     return Max;
}
void update(int p,long long x)
{
     for (;p<=VMAX;p+=LSB(p)) a[p]=max(a[p],x);
}
int main()
{
    int i,x,y;
    f>>N;
    for (i=1;i<=N;++i)
    {
        f>>x>>y;
        F[x]=1;
        F[y]=1;
        v[i].A=x;v[i].B=y;
    }
    map<int,int>::iterator it;
    for (i=1,it=F.begin();it!=F.end();++it,++i)
       it->second=i;
    for (i=1;i<=N;++i)
      v[i].nA=F[v[i].A],v[i].nB=F[v[i].B];
    sort(v+1,v+N+1,cmp);
    VMAX=v[N].nB;
    for (i=1;i<=N;++i)
    {
         long long t=query(v[i].nA)+v[i].B-v[i].A;
         sol=max(sol,t);
         update(v[i].nB,t);
    }
    g<<sol;
    return 0;
}