Cod sursa(job #1122667)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 25 februarie 2014 19:44:26
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<algorithm>
#define NMAX 100010
#define NRTIMPI 200010

using namespace std;

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

struct formatie
{
    int st, dr, x, y;
}a[NMAX];
int n, nr, timpi[NRTIMPI], best[NRTIMPI];

void Citeste()
{
    int i, nr=0;
    f>>n;
    for (i=1; i<=n; ++i)
    {
        f>>a[i].x>>a[i].y;
        timpi[++nr]=a[i].x;
        timpi[++nr]=a[i].y;
    }
}

int cauta(int x)
{
    int st=1, dr=nr, mij;

    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (timpi[mij]==x) return mij;
        else
            if (timpi[mij]>x) dr=mij-1;
            else st=mij+1;
    }
    return 0;
}

void Normalizeaza()
{
    int p=1, u=2, i;
    sort(timpi+1, timpi+n+n+1);

    while (u<=2*n)
        if (timpi[p]==timpi[u]) ++u;
        else
        {
            timpi[++p]=timpi[u]; ++u;
        }
    nr=p;
    for (i=1; i<=n; ++i)
    {
        a[i].st=cauta(a[i].x);
        a[i].dr=cauta(a[i].y);
    }
}

bool cmp(formatie A, formatie B)
{
    return A.dr<B.dr;
}

void Solve()
{
    int i, j=1, lim=timpi[nr];

    sort(a+1, a+n+1, cmp);

    for (i=1; i<=lim; ++i)
    {
        best[i]=best[i-1];
        while (a[j].dr==i)
        {
            best[i]=max(best[i], best[a[j].st]+a[j].y-a[j].x);
            ++j;
        }
    }
    g<<best[lim]<<"\n";
}

int main()
{
    Citeste();
    Normalizeaza();
    Solve();
    f.close();
    g.close();
    return 0;
}