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