Cod sursa(job #821015)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 21 noiembrie 2012 15:52:28
Problema Lacate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
#include<algorithm>
using namespace std;

struct pct
{
	int x,y;
};

const int m=100000;
pct v[100005];
int a[300000],b[300000],d[2][100005],i,j,n,mx,dx,dy,p;

bool cmp1(pct a,pct b)
{
	return a.y<b.y;
}

bool cmp2(pct a,pct b)
{
	return a.y>b.y;
}


void update(int x,int y,int k,int z,int l,int r)
{
	if ((x<=l) && (r<=y))
	{
		b[z]+=k;
		a[z]+=k;
	}
	else
	{
		int m=(l+r)/2;
		if (x<=m)
			update(x,y,k,2*z,l,m);
		if (y>m)
			update(x,y,k,2*z+1,m+1,r);
		a[z]=max(a[2*z],a[2*z+1])+b[z];
	}
}

void solve(bool k)
{
	p=1;
	for (i=1;i<=n;i++)
	{
		j=i;
		while ((j<=n) && (v[j].y==v[i].y))
		{
			update(v[j].x,v[j].x+dx,1,1,1,m);
			j++;
		}
		while (abs(v[i].y-v[p].y)>dy)
		{
			update(v[p].x,v[p].x+dx,-1,1,1,m);
			p++;
		}
		if (a[1]>d[k][v[i].y])
			d[k][v[i].y]=a[1];
		i=j-1;
	}
	while (p<=n)
	{
		update(v[p].x,v[p].x+dx,-1,1,1,m);
		p++;
	}
}

int main()
{
	ifstream f("parcele.in");
	ofstream g("parcele.out");
	f >> dx >> dy;
	f >> n;
	for (i=1;i<=n;i++)
		f >> v[i].x >> v[i].y;
	sort(v+1,v+n+1,cmp1);
	solve(0);
	sort(v+1,v+n+1,cmp2);
	solve(1);
	for (i=1;i<=m;i++)
		d[0][i]=max(d[0][i-1],d[0][i]);
	for (i=m-1;i>=1;i--)
		d[0][i]=max(d[0][i+1],d[0][i]);
	for (i=0;i<=m;i++)
	{
		mx=max(d[0][i]+d[1][i+1],mx);
		d[0][i]=0;d[1][i]=0;
	}
	swap(dx,dy);
	for (i=1;i<=n;i++)
		swap(v[i].x,v[i].y);
	sort(v+1,v+n+1,cmp1);
	solve(0);
	sort(v+1,v+n+1,cmp2);
	solve(1);
	for (i=1;i<m;i++)
		mx=max(d[0][i]+d[1][i+1],mx);
	g << mx;
	return 0;
}