比赛 |
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;
}