Cod sursa(job #542814)

Utilizator c_adelinaCristescu Adelina c_adelina Data 27 februarie 2011 00:06:03
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct nod
{long long  d,l;} v[100002];

int q[100002];

int cmp(const nod &x,const nod &y)
{	 return x.d<=y.d; }

int main()
{
	int n,i,nr=0;
	long long x,l,d=0,sol=0;
	
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d %lld %lld",&n,&x,&l);
	for (i=1;i<=n;++i)
	{
		scanf("%lld %lld",&v[nr+1].d,&v[nr+1].l);
		if (v[nr+1].d<=x) ++nr;
	}
	sort(v+1,v+nr+1,cmp);
	for (i=1;i<=nr&&d<=x;d+=l)
	{
		while ((i<=n) && (v[i].d<=d))
		{
			++q[0];
			int p=q[0];
			
			while ((p>1) && (v[q[p/2]].l<v[i].l))
			{
				q[p]=q[p/2];
				p/=2;
			}
			q[p]=i;
			++i;
		}
		if (q[0]) 
			{
				sol+=v[q[1]].l;
				--q[0];
				int p=1;
				while (p*2<=q[0])
					{
						int ok1,ok2=ok1=0;
						ok1=v[q[p*2]].l;
						if (p*2+1<=q[0]) ok2=v[q[p*2+1]].l;
						
						if ((ok1>v[q[q[0]+1]].l) && (ok2>v[q[q[0]+1]].l)) 
						{
							if (ok1>ok2) q[p]=q[p*2],p*=2; else
								q[p]=q[p*2+1],p=p*2+1;
						} else
							if (ok1>v[q[q[0]+1]].l)
								q[p]=q[p*2],p*=2; else
									if (ok2>v[q[q[0]+1]].l)
										q[p]=q[p*2],p=p*2+1; else
											break;
					}
				q[p]=q[q[0]+1];
			}
	}
	printf("%lld",sol);
	return 0;
}