记录编号	161048	评测结果	AAAAAAAAAAA
题目名称	[USACO 3.1]形成的区域 Shaping Regions	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-04-30 21:31:07	内存使用	0.34 MiB

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
class miku
{
public:
	int lx,ly;
	int rx,ry;
	int co;
}r[1010];
int n,now=0,ma=0;
LL ans[1010]={0};
int cut(int lx,int ly,int rx,int ry,int pos)
{
	//cout<<n<<endl;
	do
	{
		pos++;
		//cout<<r[pos].lx<<" "<<r[pos].ly<<" "<<r[pos].rx<<" "<<r[pos].ry<<endl;
		//cout<<rx<<" "<<ry<<" "<<lx<<" "<<ly<<endl;
		//cout<<(r[pos].lx>=rx||r[pos].ly>=ry||r[pos].rx<=lx||r[pos].ry<=ly)<<endl;
		//cout<<pos<<" "<<n<<endl;
	}while(pos<=n&&(r[pos].lx>=rx||r[pos].ly>=ry||r[pos].rx<=lx||r[pos].ry<=ly));
	if(pos>n)
	{
		ans[now]+=(ry-ly)*(rx-lx);
	//cout<<now<<" "<<ans[now]<<endl;
	}
	else
	{
		if(r[pos].lx>lx) 
		{
			cut(lx,ly,r[pos].lx,ry,pos);
			lx=r[pos].lx;
		}
		//cout<<now<<" "<<ans[now]<<endl;
		if(r[pos].rx<rx)
		{
			cut(r[pos].rx,ly,rx,ry,pos);
			rx=r[pos].rx;
		}
		//cout<<now<<" "<<ans[now]<<endl;
		if(r[pos].ly>ly)
			cut(lx,ly,rx,r[pos].ly,pos);
		//cout<<now<<" "<<ans[now]<<endl;
		if(r[pos].ry<ry)
			cut(lx,r[pos].ry,rx,ry,pos);
		//cout<<now<<" "<<ans[now]<<endl;
	}
	return 0;
}
int main()
{
	freopen("rect1.in","r",stdin);
	freopen("rect1.out","w",stdout);
	int A,B;
	scanf("%d%d%d",&A,&B,&n);
	r[0].co=1;r[0].lx=r[0].ly=0;r[0].rx=A,r[0].ry=B;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d%d",&r[i].lx,&r[i].ly,&r[i].rx,&r[i].ry,&r[i].co);
	if(r[i].co>ma) ma=r[i].co;
	}
	for(int i=n;i>=0;i--)
	{
		now=r[i].co;//cout<<n<<endl;
		cut(r[i].lx,r[i].ly,r[i].rx,r[i].ry,i);
		//cout<<now<<" "<<ans[now]<<endl;
	}
	for(int i=1;i<=1000;i++)
	{
		if(ans[i]!=0)
			printf("%d %d\n",i,ans[i]);
	}
	return 0;
}