Cod sursa(job #270349)

Utilizator andr33aradu ioana andr33a Data 3 martie 2009 22:03:21
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<fstream.h>
ifstream f("lupu.in");
ofstream g("lupu.out");
#define nmax 101000
struct elem
{
	long inf,pct;
	elem *ant,*urm;
} *c,*p;
struct vect
{
	long pt,nrv;
}a[nmax],d;

long n,x,l,y,z,w,n1,s,k;
void citire()
{
	f>>n>>x>>l;
	c=new elem;
	f>>y>>z;
	c->inf=-1;
	c->pct=0;
	c->ant=NULL;
	c->urm=NULL;
	p=c;
	elem *q=new elem;
	q->inf=(x-y)/l;
	q->pct=z;
	q->ant=c;
	q->urm=NULL;
	c->urm=q;
	c=q;
	q=new elem;
	q->inf=n+1;
	q->urm=NULL;
	q->ant=c;
	c->urm=q;
	c=q;
	for(long i=2;i<=n;i++)
	{

		f>>y>>z;
		w=(x-y)/l;
		if(w>=0)
		{
		if(c->inf>w)
		{
			while(c->inf>w)
				c=c->ant;
			while(c->inf==w&&c->pct<z)
				c=c->ant;
				elem *q=new elem;
				q->inf=w;
				q->pct=z;
				c->urm->ant=q;
				q->urm=c->urm;
				q->ant=c;
				c->urm=q;
				c=q;
		}
		else
		{
			if(c->inf<w)
			{
				while(c->inf<w)
					c=c->urm;
				while(c->inf==w&&c->pct>z)
					c=c->urm;
					elem *q=new elem;
					q->inf=w;
					q->pct=z;
					c->ant->urm=q;
					q->ant=c->ant;
					q->urm=c;
					c->ant=q;
					c=q;
			}
			else
			{
				int ok1=0,ok2=0;
				while(c->inf==w&&c->pct<z)
				{
					c=c->ant;
					ok1=1;
				}
				while(c->pct>z&&c->inf==w)
				{
					c=c->urm;
					ok2=1;
				}
				if(ok1==1||(ok1==0&&ok2==0))
				{
					elem *q=new elem;
					q->inf=w;
					q->pct=z;
					c->urm->ant=q;
					q->urm=c->urm;
					q->ant=c;
					c->urm=q;
					c=q;
				}
				else
				{
						elem *q=new elem;
						q->inf=w;
						q->pct=z;
						c->ant->urm=q;
						q->ant=c->ant;
						q->urm=c;
						c->ant=q;
						c=q;
				}
			}
		} }
	}
f.close();
}
void vector()
{
	elem *q=new elem;
	q=p;
	q=q->urm;long nr;
	while(q->urm)
	{
		nr=0;  x=q->inf;
		while(q&&q->inf==x)
		{
			if(nr<x+1)
			{
				a[n1].pt=q->pct;
				a[n1++].nrv=q->inf;
			}
			nr++;
			q=q->urm;
		}
	}
}
void sortare()
{
	long i,j;
	for(i=0;i<n1-1;i++)
		for(j=i+1;j<n;j++)
			if(a[i].pt<a[j].pt)
			{
				d=a[i];
				a[i]=a[j];
				a[j]=d;
			}
}
void suma()
{
	long i;
	s=a[0].pt;
	for(i=1;i<=n1;i++)
		if(a[i].nrv>=a[i-1].nrv)
			s+=a[i].pt;
}

int main()
{
	citire();
	vector();
	n1--;
	sortare();
	suma();
	g<<s<<'\n';
g.close();
return 0;
}