Cod sursa(job #1735298)

Utilizator Bodo171Bogdan Pop Bodo171 Data 29 iulie 2016 14:22:37
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct node
{
    int value,poz;
}arb[400005];
struct oaie
{
    int t,c;
}v[100005];
bool comp(oaie a,oaie b)
{
    return a.t<b.t;
}
int val,pozitie,n,i,j,st,step,mx,x,l,d,a;
long long sum;
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod].value=val;
        arb[nod].poz=l;
        return;
    }
    int m=(l+r)/2;
    if(pozitie<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod].value=max(arb[2*nod].value,arb[2*nod+1].value);
    if(arb[nod].value==arb[2*nod].value) arb[nod].poz=arb[2*nod].poz;
    else arb[nod].poz=arb[2*nod+1].poz;
}
void query(int nod,int l,int r)
{
    if(st<=l)
    {
        if(arb[nod].value>mx)
        {
            mx=arb[nod].value;
            pozitie=arb[nod].poz;
        }
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m);
    query(2*nod+1,m+1,r);
}
int main()
{
    ifstream f("lupu.in");
    ofstream g("lupu.out");
    f>>n>>x>>l;
    for(i=1;i<=n;i++)
    {
        f>>d>>a;
        v[i].c=a;
        v[i].t=(x-d)/l;
    }
    sort(v+1,v+n+1,comp);
    step=0;
    for(i=1;i<=n;i++)
    {
        pozitie=i;
        val=v[i].c;
        update(1,1,n);
    }
    step=0;val=-1;st=1;
    while(st<=n&&step<=n)
    {
        while(v[st].t<step&&st<=n)
            st++;
            mx=0;
        query(1,1,n);
        if(mx!=-1)sum+=mx;
        else step=n+1;
        update(1,1,n);
        step++;
    }
    g<<sum;
    return 0;
}