Cod sursa(job #333161)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 21 iulie 2009 16:43:00
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<algorithm>
using namespace std;
#define DIM 100003
struct lupu
{
    int d,a;
};
lupu a[DIM];
int n,x,l,m,maxn;
int aib[3*DIM];
int maxim (int a,int b)
{
	if (a>b)
		return a;
	return b;
}
void update (int nod,int st,int dr,int poz,int nr)
{
	if (st==dr)
		aib[nod]=nr;
	else
	{
		int mij=(st+dr)/2;
		if (poz<=mij)
			update (2*nod,st,mij,poz,nr);
		else
			update (2*nod+1,mij+1,dr,poz,nr);
		aib[nod]=maxim (aib[2*nod],aib[2*nod+1]);
	}
}
void query (int nod,int st,int dr,int in,int sf)
{
	if (st>=in && dr<=sf)
	{
		if (aib[nod]>maxn)
			maxn=aib[nod];
	}
	else
	{
		int mij=(st+dr)/2;
		if (in<=mij)
			query (2*nod,st,mij,in,sf);
		if (sf>mij)
			query (2*nod+1,mij+1,dr,in,sf);
	}
}

int cmp (lupu a,lupu b)
{
    return a.d<b.d || (a.d==b.d && a.a<b.a);
}
void read ()
{
    int i;
    scanf("%d%d%d",&n,&x,&l);
    for(i=1;i<=n;++i)
        scanf("%d%d",&a[i].d,&a[i].a);
}
int cbin_dr (int st,int dr,int prod)
{
    int mij;
    --prod;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij].d+l*prod>=x)
            dr=mij-1;
        else
            st=mij+1;
    }
    return st;
    
}
int cbin_st (int st,int dr,int prod)
{
    int mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij].d+l*prod>x)
            dr=mij-1;
        else
            st=mij+1;
    }
    return st;
    
}
void solve ()
{
    int i,ok,s=0,time=1;
    int dr=cbin_dr (1,n,time);
    int st=cbin_st (1,dr-1,time);
    while(st<=dr)
    {
        maxn=-1;
        query (1,1,n,st,dr);
		if(maxn>=0)
            s+=maxn;
        dr=st-1;
        ++time;
        for(i=dr,ok=0;ok!=1 && i>=1;--i)
            if(a[i].d+l*time<x)
                st=i+1,ok=1;
    }
    printf("%d",s);
        
}
void show ()
{
    int i;
    for(i=1;i<=n;++i)
		update (1,1,n,i,a[i].a);
}

int main ()
{
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    int i,ok,oki;
    read ();
    sort (a+1,a+1+n,cmp);
    show ();
    solve ();
    return 0;
}