比赛 20120721 评测结果 AAAAEEEEEE
题目名称 矩形覆盖a 最终得分 40
用户昵称 了反取字名我擦 运行时间 0.447 s
代码语言 C++ 内存使用 107.23 MiB
提交时间 2012-07-21 11:37:44
显示代码纯文本
#include<fstream>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<list>
#include<vector>
#include<deque>
#include<queue>
#include<map>

using namespace std;
ifstream fi("jxfgx.in");
ofstream fo("jxfgx.out");

int n,m,k,data[2001][2001]={0};
struct T
{
	int x1,x2,y1,y2;
	int cover;
	int m_level;
}tree[2001][2001];
void init(int x1,int x2,int y1,int y2,int x,int y)
{
	tree[x][y].x1=x1;
	tree[x][y].x2=x2;
	tree[x][y].y1=y1;
	tree[x][y].y2=y2;
	init(x1,(x1+x2)/2,y1,y2,x*2,y);
	init((x1+x2)/2+1,x2,y1,y2,x*2+1,y);
	init(x1,x2,y1,(y1+y2)/2,x,y*2);
	init(x1,x2,(y1+y2)/2+1,y2,x,y*2+1);
}
int c(int x1,int x2,int y1,int y2,int k,int x,int y)
{
	int ans;
	if(tree[x][y].x1!=tree[x][y].x2)
	{
		if(x1<=(tree[x][y].x1+tree[x][y].x2)/2)
		{
			if(x2>(tree[x][y].x1+tree[x][y].x2)/2)
			{
				ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
				ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
			}
			else
			{
				ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
				ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
			}
		}
		else
		{
			if(x2>(tree[x][y].x1+tree[x][y].x2)/2)
			{
				ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
				ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
			}
			else
			{
				ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
				ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
			}
		}
	}
	else
	{
		if(y1!=tree[x][y].y1||y2!=tree[x][y].y2)
		{
			if(x1<=(tree[x][y].x1+tree[x][y].x2)/2)
			{
				if(x2>(tree[x][y].x1+tree[x][y].x2)/2)
				{
					ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
					ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
				}
				else
				{
					ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
					ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
				}
			}
			else
			{
				if(x2>(tree[x][y].x1+tree[x][y].x2)/2)
				{
					ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
					ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
				}
				else
				{
					ans+=c(x1,(tree[x][y].x1+tree[x][y].x2)/2,y1,y2,k,x*2,y);
					ans+=c((tree[x][y].x1+tree[x][y].x2)/2+1,x2,y1,y2,k,x*2+1,y);
				}
			}
		}
	}
	return ans;
}
int main()
{
	fi>>n>>m>>k;
	int t1,t2,t3,t4,t5,ans;
	if(k<=100)
		while(k--)
		{
			ans=0;
			fi>>t1>>t2>>t3>>t4>>t5;
			if(t1==1)
				for(int i=t2;i<=t4;i++)
					for(int j=t3;j<=t5;j++)
						data[i][j]++;
			else
				for(int i=t2;i<=t4;i++)
					for(int j=t3;j<=t5;j++)
						data[i][j]--;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=m;j++)
					if(data[i][j])
						ans++;
			fo<<ans<<endl;
		}
	else
	{
		init(1,n,1,m,1,1);
		int temp[5];
		while(k--)
		{
			fi>>temp[0]>>temp[1]>>temp[2]>>temp[3]>>temp[4];
			if(temp[0]==1)
				fo<<c(temp[1],temp[3],temp[2],temp[4],1,1,1);
			else
				fo<<c(temp[1],temp[3],temp[2],temp[4],-1,1,1);
		}
	}
	fi.close();
	fo.close();
	return 0;
}