Cod sursa(job #517132)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 27 decembrie 2010 21:06:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int a[200001],v[200001],v2[100001],r[200001],ind[200001],d[200001],n,x;

inline int cmp(int i,int j)
{
    return v[i]<v[j];
}

inline int cmp2(int i,int j)
{
    return v2[i]<v2[j];
}

int main()
{
    int i,j=0;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d%d",&v[2*i-1],&v[2*i]);
        ind[2*i-1]=2*i-1;
        ind[2*i]=2*i;
    }
    sort(ind+1,ind+2*n+1,cmp);
    for (i=1;i<=2*n;++i)
    {
        if (v[ind[i]]==v[ind[i-1]]) a[i]=x;
        else
        {
            ++x;
            r[x]=v[ind[i]];
            a[i]=x;
        }
    }
    for (i=1;i<=2*n;++i) v[ind[i]]=a[i];
    for (i=2;i<=2*n;i+=2) v2[i/2]=v[i];
    for (i=1;i<2*n;i+=2) v[i/2+1]=v[i];
    for (i=1;i<=n;++i) ind[i]=i;
    sort(ind+1,ind+n+1,cmp2);
    for (i=1;i<=n;++i) a[i]=v[ind[i]];
    for (i=1;i<=n;++i) v[i]=a[i];
    for (i=1;i<=n;++i) a[i]=v2[ind[i]];
    for (i=1;i<=n;++i) v2[i]=a[i];
    for (i=1;i<=x;++i)
    {
        d[i]=d[i-1];
        while (v2[j+1]==i)
        {
            ++j;
            if (d[i]<d[v[j]]+r[v2[j]]-r[v[j]]) d[i]=d[v[j]]+r[v2[j]]-r[v[j]];
        }
    }
    printf("%d",d[x]);
    return 0;
}