比赛 |
20161116 |
评测结果 |
AAAAAAAAAA |
题目名称 |
删除他们! |
最终得分 |
100 |
用户昵称 |
cwm大佬%%% |
运行时间 |
1.684 s |
代码语言 |
C++ |
内存使用 |
53.70 MiB |
提交时间 |
2016-11-16 10:23:57 |
显示代码纯文本
#include<cstdio>
const int NM=1000000+10;
int n,m,q;
struct SEG{
struct P{
bool pudown;
int delta,sum;
int l,r;
int lc,rc;
};
P tree[NM*2];
int top;
SEG(){top=0;}
int build_tree(int l,int r){
int p=top++;
P &now=tree[p];
now=(P){0,0,0,l,r,-1,-1};
if(l<r){
now.lc=build_tree(l,(l+r)/2);
now.rc=build_tree((l+r)/2+1,r);
}
return p;
}
void push_down(int p){
P &now=tree[p];
if(now.pudown==0)return;
tree[now.lc].pudown=1;
tree[now.lc].delta=now.delta;
tree[now.lc].sum=now.delta*(tree[now.lc].r-tree[now.lc].l+1);
tree[now.rc].pudown=1;
tree[now.rc].delta=now.delta;
tree[now.rc].sum=now.delta*(tree[now.rc].r-tree[now.rc].l+1);
now.sum=tree[now.lc].sum+tree[now.rc].sum;
now.pudown=0;
}
void change(int l,int r,int delta,int p=0){
if(p==-1)return;
P &now=tree[p];
if(now.l>r||now.r<l)return;
if(now.l>=l&&now.r<=r){
now.pudown=1;
now.delta=delta;
now.sum=now.delta*(now.r-now.l+1);
}else{
push_down(p);
change(l,r,delta,now.lc);
change(l,r,delta,now.rc);
now.sum=tree[now.lc].sum+tree[now.rc].sum;
}
}
int query(int l,int r,int p=0){
if(p==-1)return 0;
P &now=tree[p];
if(now.l>r||now.r<l)return 0;
if(now.l>=l&&now.r<=r)return now.sum;
push_down(p);
return query(l,r,now.lc)+query(l,r,now.rc);
}
//void put(){for(int i=0;i<top;i++)printf("%d %d : %d %d %d\n",tree[i].l,tree[i].r,tree[i].pudown,tree[i].delta,tree[i].sum);putchar('\n');}
};
SEG G;
int hash(int x,int y){return x*m+y;}
void _hash(int sum,int &x,int &y){
y=sum%m;
x=sum/m;
}
int main()
{
freopen("deleteit.in","r",stdin);
freopen("deleteit.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
G.build_tree(0,n*m-1);
G.change(0,m*n-1,1);
for(int i=0;i<q;i++){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=x1;i<=x2;i++)G.change(hash(i,y1),hash(i,y2),0);
int tot=G.query(hash(x1,y1),n*m-1);
G.change(hash(x1,y1),n*m-1,0);
G.change(hash(x1,y1),hash(x1,y1)+tot-1,1);
}
printf("%d\n",G.query(0,m*n-1));
return 0;
}