比赛 |
20120721 |
评测结果 |
AAAATTTEEE |
题目名称 |
矩形覆盖a |
最终得分 |
40 |
用户昵称 |
Makazeu |
运行时间 |
3.763 s |
代码语言 |
C++ |
内存使用 |
0.32 MiB |
提交时间 |
2012-07-21 11:28:44 |
显示代码纯文本
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=2222;
int N,M,K,f,x1,y1,x2,y2,ans;
class SegTree
{
public:
int L,R,Mid,Area,Wall;
SegTree *lc,*rc;
void clear()
{
L=0,R=0,Mid=0,Wall=0,Area=0;
lc=NULL,rc=NULL;
}
};
SegTree* Root[MAXN];
void build(SegTree *pnt,int l,int r)
{
pnt->clear(); pnt->L=l,pnt->R=r;
pnt->Mid=(l+r)/2; if(l==r) return;
pnt->lc=new SegTree;
pnt->rc=new SegTree;
build(pnt->lc,l,pnt->Mid);
build(pnt->rc,pnt->Mid+1,r);
}
void Insert(SegTree *pnt,int l,int r,bool flag)
{
if(pnt->L==r && pnt->R==r)
{
if(flag) pnt->Wall++; else pnt->Wall--;
if(l==r)
{
if(pnt->Wall) pnt->Area=1;
else pnt->Area=0;
return;
}
if(!pnt->Wall) pnt->Area=pnt->lc->Area+pnt->rc->Area;
return;
}
if(r<=pnt->Mid)
{
Insert(pnt->lc,l,r,flag);
if(!pnt->Wall) pnt->Area=pnt->lc->Area+pnt->rc->Area;
return;
}
if(l>=pnt->Mid+1)
{
Insert(pnt->rc,l,r,flag);
if(!pnt->Wall) pnt->Area=pnt->lc->Area+pnt->rc->Area;
return;
}
Insert(pnt->lc,l,pnt->Mid,flag);
Insert(pnt->rc,pnt->Mid+1,r,flag);
if(!pnt->Wall) pnt->Area=pnt->lc->Area+pnt->rc->Area;
return;
}
int Find(SegTree *pnt,int l,int r)
{
if(pnt->L==r && pnt->R==r)
return pnt->Area;
if(r<=pnt->Mid) return Find(pnt->lc,l,r);
if(l>=pnt->Mid+1) return Find(pnt->rc,l,r);
return Find(pnt->lc,l,pnt->Mid)+Find(pnt->rc,pnt->Mid+1,r);
}
int main()
{
freopen("jxfgx.in","r",stdin);
freopen("jxfgx.out","w",stdout);
scanf("%d %d %d\n",&N,&M,&K);
for(int i=1;i<=M;i++)
{
Root[i]=new SegTree;
build(Root[i],1,N);
}
for(int i=1;i<=K;i++)
{
scanf("%d %d %d %d %d\n",&f,&x1,&y1,&x2,&y2);
if(f==1)
{
for(int j=y1;j<=y2;j++)
Insert(Root[j],x1,x2,1);
}
else
{
for(int j=y1;j<=y2;j++)
Insert(Root[j],x1,x2,0);
}
ans=0;
for(int j=1;j<=M;j++)
ans+=Find(Root[j],1,N);
printf("%d\n",ans);
}
return 0;
}