Cod sursa(job #490932)

Utilizator edp100Edp100 edp100 Data 8 octombrie 2010 21:02:57
Problema Stalpi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

vector <int> start[100006],final[100006];
int heap[100006],n,viz[100006],nod,d[100006];

struct stalp
{
    int x,cost,st,dr;
};
stalp v[100006];

inline int formula(int val)
{
    return (d[v[val].st-1]+v[val].cost);
}

inline int cmp(const stalp& a,const stalp& b)
{
    return a.x<b.x;
}

int compar(int n1,int n2)
{
    return formula(heap[n1])>formula(heap[n2]);
}

void sift(int poz)
{
    if(compar(poz/2,poz))
    {
        int aux;
        aux=heap[poz];
        heap[poz]=heap[poz/2];
        heap[poz/2]=aux;
        viz[heap[poz]]=poz;
        viz[heap[poz/2]]=poz/2;
        sift(poz/2);
    }
}

void percolate(int poz)
{
    int c1=0,c2=0,c3=1,aux;
    if(2*poz<=nod)
        c1=compar(poz,2*poz);
    if(2*poz<nod)
    {
        c2=compar(poz,2*poz);
        c3=compar(2*poz,2*poz+1);
    }
    if(c1 && !c3)
    {
        //2*poz,poz
        aux=heap[poz];
        heap[poz]=heap[2*poz];
        heap[2*poz]=aux;
        viz[heap[poz]]=poz;
        viz[heap[2*poz]]=2*poz;
        sift(2*poz);
    }
    else
        if(c2)
        {
            aux=heap[poz];
            heap[poz]=heap[2*poz+1];
            heap[2*poz+1]=aux;
            viz[heap[poz]]=poz;
            viz[heap[2*poz+1]]=2*poz+1;
            sift(2*poz+1);
        }
}

void insert(int val)
{
    heap[++nod]=val;
    viz[val]=nod;
    sift(nod);
}

void sterge(int val)
{
    heap[viz[val]]=heap[nod];
    viz[heap[nod]]=viz[val];
    nod--;
    percolate(viz[val]);
    sift(viz[val]);
}


int main ()
{
    int i,j,inc,sf,sol,mij,lim;
    freopen("stalpi.in","r",stdin);
    freopen("stalpi.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d%d%d",&v[i].x,&v[i].cost,&v[i].st,&v[i].dr);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        inc=1;sf=i;
        while(inc<=sf)
        {
            mij=(inc+sf)/2;
            if(v[mij].x<v[i].x-v[i].st)
                inc=mij+1;
            else
            {
                sol=mij;
                sf=mij-1;
            }
        }
        v[i].st=sol;
        ///////
        inc=i;sf=n;
        while(inc<=sf)
        {
            mij=(inc+sf)/2;
            if(v[mij].x>v[i].x+v[i].dr)
                sf=mij-1;
            else
            {
                sol=mij;
                inc=mij+1;
            }
        }
        v[i].dr=sol;
    }
    for(i=1;i<=n;i++)
    {
        start[v[i].st].push_back(i);
        final[v[i].dr+1].push_back(i);
    }
    for(i=1;i<=n;i++)
    {
        lim=start[i].size();
        for(j=0;j<lim;j++)
            insert(start[i][j]);
        lim=final[i].size();
        for(j=0;j<lim;j++)
            sterge(final[i][j]);
        d[i]=formula(heap[1]);;
    }
    printf("%d\n",d[n]);
    return 0;
}