Cod sursa(job #340542)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 15 august 2009 11:55:14
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <vector>
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");
int cmpA(I X,I Y) {return X.A<Y.A;}
int cmpB(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);
}
vector<int> x;
#define pb push_back
int main()
{
    int i;
    f>>N;
    for (i=1;i<=N;++i)
    {
        f>>v[i].A>>v[i].B;
        x.pb(v[i].A);
        x.pb(v[i].B);
    }
    sort(x.begin(),x.end());
    unique(x.begin(),x.end());
    sort(v+1,v+N+1,cmpA);
    size_t j;
    for (i=1,j=0;i<=N;++i)
    {
        for (;x[j]<v[i].A;++j);
        v[i].nA=j+1;
    }
    sort(v+1,v+N+1,cmpB);
    for (i=1,j=0;i<=N;++i)
    {
        for (;x[j]<v[i].B;++j);
        v[i].nB=j+1;
    }
    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;
}