Cod sursa(job #837817)

Utilizator cat_red20Vasile Ioana cat_red20 Data 18 decembrie 2012 18:35:43
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int best[100001],n,p[100001],tmax,nr;
struct timp
{
    int a,b;
}v[100001];

int cmp(timp x,timp y)
{
    return x.b<y.b;
}

void citire()
{
    freopen("heavymetal.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&v[i].a,&v[i].b);
        p[2*i-1]=v[i].a;
        p[2*i]=v[i].b;
    }
}

int cauta(int x)
{
    int m,st=1,sf=nr;
    while(st<=sf)
    {
        m=(st+sf)/2;
        if(p[m]==x)
        return m;
        if(p[m]<x)
        st=m+1;
        else
        sf=m-1;
    }
}

void normalizare()
{
    nr=1;
    for(int i=2;i<=2*n;i++)
    {
        if(p[i]!=p[i-1])
        p[++nr]=p[i];
    }

    for(int i=1;i<=n;i++)
    {
        v[i].a=cauta(v[i].a);
        v[i].b=cauta(v[i].b);
    }
}

int maxim(int a,int b)
{
    if(a>b)
    return a;
    return b;
}

void din()
{
    int t=1;
    for(int i=1;i<=nr;i++)
    {
        best[i]=best[i-1];
        while(v[t].b<i)
        t++;
        while(v[t].b==i)
        {
            best[i]=maxim(best[i],best[v[t].a]+p[v[t].b]-p[v[t].a]);
            t++;
        }
    }
}

void afisare()
{
    freopen("heavymetal.out","w",stdout);
    printf("%d",best[nr]);
}

int main()
{
    citire();
    sort(v+1,v+n+1,cmp);
    sort(p,p+2*n+1);
    normalizare();
    din();
    afisare();
    return 0;
}