Cod sursa(job #1384340)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 11 martie 2015 00:40:46
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>
#define nmax 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval{int x;int y;int z;};
int n,t,v[nmax],d[nmax*2];
interval r[nmax];



int cautbin(int x)
{
    int p,q=0;
    for (p=1<<19;p;p>>=1)
        if (q+p<=t&&v[q+p]<=x)
            q+=p;
    if (v[q]==x)
        return q;
    return 0;
}
bool cmp(const interval &a, const interval &b)
{
    return a.y<b.y;

}
int main()
{
    int i,j;
    f>>n;
    for (i=1;i<=n;i++) {
        f>>r[i].x>>r[i].y;
        if (!cautbin(r[i].x))
            v[++t]=r[i].x;
        if (!cautbin(r[i].y))
            v[++t]=r[i].y;
    }
    sort(v+1,v+t+1);
    for (i=1;i<=n;i++) {
        r[i].z=r[i].y-r[i].x;
        r[i].x=cautbin(r[i].x);
        r[i].y=cautbin(r[i].y);
    }
    sort(r+1,r+n+1,cmp);
    j=1;
    for (i=1;i<=t;i++) {
        d[i]=max(d[i],d[i-1]);
        while (j<=n&&r[j].y<i)
            j++;
        while (j<=n&&r[j].y==i) {
            d[i]=max(d[i],d[r[j].x]+r[j].z);
            j++;
        }
    }
    g<<d[t]<<'\n';
    return 0;
}