Cod sursa(job #378538)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 28 decembrie 2009 20:53:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,s,help[100001][2];
struct muzic
{
    int val,tip,nra,timp;
};
muzic v[200001];
int cmp (muzic a,muzic b)
{
    if(a.val==b.val)
        return (a.tip>b.tip);
    return(a.val<b.val);
}
int main ()
{
    int i,p,nr=0,a,b,poz,n2;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    p=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        v[++nr].val=a;
        v[nr].tip=1;
        v[nr].nra=++p;
        v[++nr].val=b;
        v[nr].tip=2;
        v[nr].nra=p;
    }
    n2=2*n;
    sort(v+1,v+n2+1,cmp);
    for(i=1;i<=2*n;i++)
        help[v[i].nra][v[i].tip-1]=i;
    s=0;
    for(i=1;i<=2*n;i++)
    {
        if(v[i].tip==1)
        {
            poz=v[i].nra;
            poz=help[poz][1];
            v[poz].timp=s+v[poz].val-v[i].val;
        }
        else
        {
            if(v[i].timp>s)
                s=v[i].timp;
        }   //else
    }   //for
    printf("%d\n",s);
    return 0;
}