比赛 20110725 评测结果 AAAAAAAATT
题目名称 失落的猴子 最终得分 80
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-25 12:38:29
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=1111;

int n,m,i,j,k,Q,ps=0,co[MAXN][MAXN],X1,Y1,X2,Y2;

struct xds
{
	int xa,ya,xb,yb,C;
	xds *c[4];
	inline void breed()
	{
		if (c[0])
		c[0]->C=c[1]->C=C;
		if (c[2])
		c[2]->C=c[3]->C=C;
		C=-1;
	}
}T[3000000],*root=T;

void mkt(xds *p,int xa,int ya,int xb,int yb)
{
	p->xa=xa; p->xb=xb;
	p->ya=ya; p->yb=yb;
	p->C=-1;
	if (xb>xa || yb>ya)
	{
		int midx,midy;
		midx=(xa+xb)>>1;
		midy=(ya+yb)>>1;
		if (xb==xa)
		{
			++ps;
			p->c[0]=T+ps;
			mkt(p->c[0],xa,ya,xa,midy);
			++ps;
			p->c[1]=T+ps;
			mkt(p->c[1],xa,midy+1,xa,yb);
		}
		if (yb==ya)
		{
			++ps;
			p->c[0]=T+ps;
			mkt(p->c[0],xa,ya,midx,ya);
			++ps;
			p->c[1]=T+ps;
			mkt(p->c[1],midx+1,ya,xb,ya);
		}
		if (ya!=yb && xa!=xb)
		{
			++ps;
			p->c[0]=T+ps;
			mkt(p->c[0],xa,ya,midx,midy);
			++ps;
			p->c[1]=T+ps;
			mkt(p->c[1],xa,midy+1,midx,yb);
			++ps;
			p->c[2]=T+ps;
			mkt(p->c[2],midx+1,ya,xb,midy);
			++ps;
			p->c[3]=T+ps;
			mkt(p->c[3],midx+1,midy+1,xb,yb);
		}
	}
}

void ins(xds *p)
{
	if (p->xa>X2 || p->xb<X1 || p->ya>Y2 || p->yb<Y1) return;
	if (p->xa>=X1 && p->xb<=X2 && p->ya>=Y1 && p->yb<=Y2)
	{
		p->C=k;
		return;
	}
	if (p->C!=-1) p->breed();
	for (int i=0;i<4;i++)
		if (p->c[i]) ins(p->c[i]);
}

void dfs(xds *p)
{
	if (p->xa==p->xb && p->ya==p->yb)
	{
		co[p->xa][p->ya]=(p->C==-1)?0:p->C;
		return;
	}
	if (p->C!=-1) p->breed();
	for (int i=0;i<4;i++)
		if (p->c[i]) dfs(p->c[i]);
}

int main()
{
	freopen("lostmonkey.in","r",stdin);
	freopen("lostmonkey.out","w",stdout);
	scanf("%d%d%d",&n,&m,&Q);
	mkt(root,1,1,n,m);
	while (Q--)
	{
		scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&k);
		ins(root);
	}
	dfs(root);
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
			printf("%d",co[i][j]);
		printf("\n");
	}
	return 0;
}