记录编号	26765	评测结果	AAAAAAAATT
题目名称	失落的猴子	最终得分	80
用户昵称	PurpleShadow	是否通过	未通过
代码语言	C++	运行时间	4.358 s
提交时间	2011-07-26 08:15:07	内存使用	4.08 MiB

#include <cstdio>
const int N=1001;
struct node
{
	int x1,y1,x2,y2;
	int o;
	node* c[4];
	node(const int &_x1,const int &_y1,const int &_x2,const int &_y2,const int &_o):
	x1(_x1),y1(_y1),x2(_x2),y2(_y2),o(_o){c[0]=c[1]=c[2]=c[3]=0;}
};
node* root;
int n,m,k;
void build(int x1,int x2,int y1,int y2,node* &p)
{
	if (x1>x2||y1>y2) return;
	p=new node(x1,y1,x2,y2,-1);
	if (x1==x2&&y1==y2)
	{
		p->o=0;
		return;
	}
	int m1=(x1+x2)>>1,m2=(y1+y2)>>1;
	build(x1,m1,y1,m2,p->c[0]);
	build(x1,m1,m2+1,y2,p->c[1]);
	build(m1+1,x2,y1,m2,p->c[2]);
	build(m1+1,x2,m2+1,y2,p->c[3]);
}
void init()
{
	scanf("%d%d%d",&n,&m,&k);
	build(1,n,1,m,root);
}
inline void push_down(node* p)
{
	if (p->o==-1) return;
	bool flag=1;
	if (p->c[0]) p->c[0]->o=p->o,flag=0;
	if (p->c[1]) p->c[1]->o=p->o,flag=0;
	if (p->c[2]) p->c[2]->o=p->o,flag=0;
	if (p->c[3]) p->c[3]->o=p->o,flag=0;
	if (!flag) p->o=-1;
}
void Cover(int xa,int xb,int ya,int yb,int o,node* p)
{
	if (!p) return;
	push_down(p);
	if (xa<=p->x1&&ya<=p->y1&&xb>=p->x2&&yb>=p->y2)
	{
		p->o=o;
		return;
	}
	int m1=(p->x1+p->x2)>>1,m2=(p->y1+p->y2)>>1;
	if (xa<=m1&&ya<=m2) Cover(xa,xb,ya,yb,o,p->c[0]);
	if (xa<=m1&&yb>m2) Cover(xa,xb,ya,yb,o,p->c[1]);
	if (xb>m1&&ya<=m2) Cover(xa,xb,ya,yb,o,p->c[2]);
	if (xb>m1&&yb>m2) Cover(xa,xb,ya,yb,o,p->c[3]);
}
int G[N][N];
void show(node *p)
{
	if (!p) return;
	push_down(p);
	if (p->x1==p->x2&&p->y1==p->y2)
	{
		G[p->x1][p->y1]=p->o;
		return;
	}
	show(p->c[0]);
	show(p->c[1]);
	show(p->c[2]);
	show(p->c[3]);
}
void slove()
{
	int xa,ya,xb,yb,l;
	while (k--)
	{
		scanf("%d%d%d%d%d",&xa,&ya,&xb,&yb,&l);
		Cover(xa,xb,ya,yb,l,root);
	}
	show(root);
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
			printf("%d",G[i][j]);
		printf("\n");
	}
}
int main()
{
freopen("lostmonkey.in","r",stdin);
freopen("lostmonkey.out","w",stdout);
	init();
	slove();
	return 0;
}