注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2810][Apio2012]kunai  

2015-06-22 16:31:37|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2810: [Apio2012]kunai

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 78  Solved: 30
[Submit][Status][Discuss]

Description

Input

从标准输入读入数据。 
第一行包含两个被空格隔开的整数 W, H,表示广场的尺寸为W列H行。 
第二行包含一个整数N,表示忍者的数量。 
接下来N行中,第 i行有三个以空格分隔的整数 X
i,Yi, D i, 表示第i个忍者处在从左往右的 X
i列、从上往下的第Yi行,任何两个忍者不在同一个位置。第i个忍者面向的方向由Di

Di = 0,表示忍者向右; 
Di = 1,表示忍者向上; 
Di = 2,表示忍者向左; 
Di = 3,表示忍者向下。

Output

输出一个整数,表示经过足够长的时间之后,在这个  W     H 的广场中被苦无经过被苦无经过的格子数量。

Sample Input

5 4 5 3 3 2 3 2 0 4 2 2 5 4 1 1 1 3

Sample Output

11

HINT

1  ≤N ≤ 100,000 忍者数;
1  ≤W ≤ 1,000,000,000 列数; 
1  ≤H ≤ 1,000,000,000 行数; 
1  ≤Xi ≤ W,1 ≤ Yi ≤ H 坐标范围。

Solution

终于做完了这道丧题!
我是这么想的:

首先分四类处理:
1st:0和2撞
    按照x - y排序,x值相同的拎出来做一遍
    比如像这样: -> -> <- -> -> <- <- <-
    每一个<-和它左边最靠近它的->连在一起塞到堆里面,表示如果只有这一行存在的话,这两个会同归。
    所以就是一个类似括号序列的东西,入栈出栈搞一下
2nd:1和3撞
    按照y - x排序
3rd:1和2撞,0和3撞
    按照x+y - y-x排序
4th:0和1撞,2和3撞
    按照y-x - x+y排序

然后把堆里面的东西按时间顺序一个个取出来,如果两端有一个已经挂了就扔掉吧,两端都在就加进去,标记一下两个苦无活了多久。
//咦不对啊,这不是直接sort就好了嘛为什么还要堆???

然后我们既然已经知道了每个苦无存活的时间,就可以弄出一个个宽度为1的矩形出来,然后写一个矩形面积并就完事了~

都写完好像才不到4k。。。然后心里想为什么大家都写了这么长。。。
调完样例交一发,第一个点,Wa!尼玛= = = = 

于是抠了份std下来对拍,随机数据毫无问题。。。
让我们来构造吧。所有苦无都在某些特定的行和列上。果然直接Wa
10 10
9
3 3 0
3 6 0
3 9 3
6 3 0
6 6 0
6 9 2
9 3 2
9 6 2
9 9 1
ans=27
注意到5和8先撞了,然后9只能和1撞。也就是说,随着一个苦无的消失,很可能有另外的苦无相撞的目标发生改变。
怎么办呢?弄四个链表分别记录上述四种情况,比如5和8撞了,9的目标会改成1,所以pre[4][5]=1 //在第四种情况

然后改完就(W)A了,发现矩形面积并算答案的时候估计不会爆int然而实际随便爆。。。

然后花了一会儿功夫把代码压起来,就变成了3k+ 真是2333本来是3333B的BZOJ上1个tab算4个空格...
个人感觉那份代码毒瘤。
不过之前第一发A的代码可读性还是很强的所有变量名都(基本)拼全了
写完真是神清气爽= = 

Code

第一发:
/**************************************************************
    Problem: 2810
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2512 ms
    Memory:21696 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,m,t,cnt,ht,dy[N<<1],del[N],pre[4][N],nxt[4][N];double time_v[N];
struct P{int x,y,c,id;}p[N],s[N];
#define PP const P&
bool operator<(PP a,PP b){return a.id<b.id;}
bool cmp1(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
bool cmp2(PP a,PP b){return a.y<b.y||a.y==b.y&&a.x<b.x;}
bool cmp3(PP a,PP b){return a.x+a.y<b.x+b.y||a.x+a.y==b.x+b.y&&a.y-a.x<b.y-b.x;}
bool cmp4(PP a,PP b){return a.y-a.x<b.y-b.x||a.y-a.x==b.y-b.x&&a.x+a.y<b.x+b.y;}
 
struct H{int x,y,c;double t;}tmp;
bool operator<(const H&a,const H&b){return a.t>b.t;}
__gnu_pbds::priority_queue<H>q;
struct D{int x,l,r,p;}d[N<<1];
#define addrect(a,b,l,r) d[++cnt]=(D){a,l,r,1},d[++cnt]=(D){b,l,r,-1},dy[++ht]=l,dy[++ht]=r
bool operator<(const D&a,const D&b){return a.x<b.x||a.x==b.x&&a.p>b.p;}
int len[1<<19],L[1<<19],R[1<<19],sum[1<<19];long long ans;
void bt(int o,int l,int r){
    L[o]=dy[l],R[o]=dy[r];int mid=l+r>>1;
    if(l+1<r)bt(o<<1,l,mid),bt(o<<1|1,mid,r);
    else L[o<<1]=R[o<<1]=L[o],L[o<<1|1]=R[o<<1|1]=R[o];
}
#define mt(o) len[o]=sum[o]?R[o]-L[o]:len[o<<1]+len[o<<1|1]
void upd(int o,int l,int r,int p){
    if(l<=L[o]&&R[o]<=r){sum[o]+=p,mt(o);return;}
    if(l<R[o<<1])upd(o<<1,l,r,p);
    if(L[o<<1|1]<r)upd(o<<1|1,l,r,p);mt(o);
}
int main(){
    m=F(),n=F(),t=F();
    for(int i=1,x,y;i<=t;i++)y=F(),x=F(),p[i]=(P){x,y,F(),i};
#define ins_event(case,ft_s,ft_i,ft_las,c_begin,c_end,dis) \
    for(register int i=1,top=0,las=0;i<=t;i++){\
        while(top&&ft_s!=ft_i)top--;\
        if(ft_las!=ft_i)las=0;\
        if(p[i].c==c_begin){\
            pre[case][p[i].id]=s[top].id,nxt[case][s[top].id]=p[i].id;\
            s[++top]=p[i];\
        }\
        else if(p[i].c==c_end){\
            nxt[case][p[i].id]=p[las].id,pre[case][p[las].id]=p[i].id,las=i;\
            if(top)q.push((H){s[top].id,p[i].id,case,dis}),top--;\
        }\
    }
    /*Case-0  0-2*/
    std::sort(p+1,p+1+t,cmp1);
    ins_event(0,s[top].x,p[i].x,p[las].x,0,2,(p[i].y-s[top].y)*0.5);
    /*Case-1  1-3*/
    std::sort(p+1,p+1+t,cmp2);
    ins_event(1,s[top].y,p[i].y,p[las].y,3,1,(p[i].x-s[top].x)*0.5);
    /*Case-2  1-2 && 0-3*/
    std::sort(p+1,p+1+t,cmp3);
    ins_event(2,s[top].x+s[top].y,p[i].x+p[i].y,p[las].x+p[las].y,1,2,p[i].y-s[top].y);
    ins_event(2,s[top].x+s[top].y,p[i].x+p[i].y,p[las].x+p[las].y,0,3,p[i].y-s[top].y);
    /*Case-3  0-1 && 2-3*/
    std::sort(p+1,p+1+t,cmp4);
    ins_event(3,s[top].y-s[top].x,p[i].y-p[i].x,p[las].y-p[las].x,0,1,p[i].y-s[top].y);
    ins_event(3,s[top].y-s[top].x,p[i].y-p[i].x,p[las].y-p[las].x,3,2,p[i].y-s[top].y);
 
    std::sort(p+1,p+1+t);
    while(!q.empty()){
        tmp=q.top(),q.pop();
        if((time_v[tmp.x]==0||time_v[tmp.x]==tmp.t)
         &&(time_v[tmp.y]==0||time_v[tmp.y]==tmp.t))
        time_v[tmp.x]=time_v[tmp.y]=tmp.t,del[tmp.x]=del[tmp.y]=1;
#define getnext {\
    if(tmp.c==0)tmp.t=0.5*(p[tmp.y].y-p[tmp.x].y);\
    else if(tmp.c==1)tmp.t=0.5*(p[tmp.y].x-p[tmp.x].x);\
    else tmp.t=p[tmp.y].y-p[tmp.x].y;\
    q.push(tmp);\
}
        else if(time_v[tmp.x]!=0&&time_v[tmp.x]!=tmp.t){
            while(tmp.x=pre[tmp.c][tmp.x],del[tmp.x]);
            if(tmp.x)getnext;
        }
        else if(time_v[tmp.y]!=0&&time_v[tmp.y]!=tmp.t){
            while(tmp.y=pre[tmp.c][tmp.y],del[tmp.y]);
            if(tmp.y)getnext;
        }
    }
    for(register int i=1,to;i<=t;i++)
    if(to=time_v[i],p[i].c==0){
        if(time_v[i]==0)to=m;else to+=p[i].y;
        addrect(p[i].x-1,p[i].x,p[i].y-1,to);
    }else if(p[i].c==1){
        if(time_v[i]==0)to=1;else to=p[i].x-to;
        addrect(to-1,p[i].x,p[i].y-1,p[i].y);
    }else if(p[i].c==2){
        if(time_v[i]==0)to=1;else to=p[i].y-to;
        addrect(p[i].x-1,p[i].x,to-1,p[i].y);
    }else{
        if(time_v[i]==0)to=n;else to+=p[i].x;
        addrect(p[i].x-1,to,p[i].y-1,p[i].y);
    }
    std::sort(dy+1,dy+1+ht),ht=std::unique(dy+1,dy+1+ht)-dy-1;
    std::sort(d+1,d+1+cnt),bt(1,1,ht);
    for(register int i=1;i<=cnt;i++)upd(1,d[i].l,d[i].r,d[i].p),ans+=1LL*len[1]*(d[i+1].x-d[i].x);
    printf("%lld\n",ans);
}
一份不到70行的毒瘤代码:
/**************************************************************
    Problem: 2810
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2452 ms
    Memory:20132 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
#define ri register int
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
char ch,B[1<<15],*S=B,*T=B;int F(){
    while(ch=getc(),ch<'0'||ch>'9');ri aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,m,t,ct,ht,dy[N<<1],del[N],pr[4][N];double tv[N];
struct P{int x,y,c,id;}p[N],s[N];
#define PP const P&
bool operator<(PP a,PP b){return a.id<b.id;}
bool c1(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
bool c2(PP a,PP b){return a.y<b.y||a.y==b.y&&a.x<b.x;}
bool c3(PP a,PP b){return a.x+a.y<b.x+b.y||a.x+a.y==b.x+b.y&&a.y-a.x<b.y-b.x;}
bool c4(PP a,PP b){return a.y-a.x<b.y-b.x||a.y-a.x==b.y-b.x&&a.x+a.y<b.x+b.y;}
struct H{int x,y,c;double t;};
bool operator<(const H&a,const H&b){return a.t>b.t;}
__gnu_pbds::priority_queue<H>q;
struct D{int x,l,r,p;}d[N<<1];
#define ar(a,b,l,r) d[++ct]=(D){a,l,r,1},d[++ct]=(D){b,l,r,-1},dy[++ht]=l,dy[++ht]=r
bool operator<(const D&a,const D&b){return a.x<b.x||a.x==b.x&&a.p>b.p;}
int ln[1<<19],L[1<<19],R[1<<19],sm[1<<19];long long ans;
void bt(ri o,ri l,ri r){
    if(L[o]=dy[l],R[o]=dy[r],l+1<r)bt(o<<1,l,l+r>>1),bt(o<<1|1,l+r>>1,r);else L[o<<1]=R[o<<1]=L[o],L[o<<1|1]=R[o<<1|1]=R[o];
}
#define mt ln[o]=sm[o]?R[o]-L[o]:ln[o<<1]+ln[o<<1|1]
void up(ri o,ri l,ri r,ri p){
    if(l<=L[o]&&R[o]<=r){sm[o]+=p,mt;return;}
    if(l<R[o<<1])up(o<<1,l,r,p);
    if(L[o<<1|1]<r)up(o<<1|1,l,r,p);mt;
}
#define ie(cs,fs,fi,fl,cb,ce,ds) \
for(ri i=1,tp=0,l=0;i<=t;i++){\
    while(tp&&fs!=fi)tp--;fl!=fi?l=0:1,p[i].c==cb?pr[cs][p[i].id]=s[tp].id,s[++tp]=p[i],1:\
    p[i].c==ce?pr[cs][p[l].id]=p[i].id,l=i,tp?q.push((H){s[tp].id,p[i].id,cs,ds}),tp--:1:1;\
}
main(){
    m=F(),n=F(),t=F();
    for(ri i=1,x,y;i<=t;i++)y=F(),x=F(),p[i]=(P){x,y,F(),i};
    std::sort(p+1,p+1+t,c1);ie(0,s[tp].x,p[i].x,p[l].x,0,2,(p[i].y-s[tp].y)*0.5);
    std::sort(p+1,p+1+t,c2);ie(1,s[tp].y,p[i].y,p[l].y,3,1,(p[i].x-s[tp].x)*0.5);
    std::sort(p+1,p+1+t,c3);ie(2,s[tp].x+s[tp].y,p[i].x+p[i].y,p[l].x+p[l].y,1,2,p[i].y-s[tp].y);ie(2,s[tp].x+s[tp].y,p[i].x+p[i].y,p[l].x+p[l].y,0,3,p[i].y-s[tp].y);
    std::sort(p+1,p+1+t,c4);ie(3,s[tp].y-s[tp].x,p[i].y-p[i].x,p[l].y-p[l].x,0,1,p[i].y-s[tp].y);ie(3,s[tp].y-s[tp].x,p[i].y-p[i].x,p[l].y-p[l].x,3,2,p[i].y-s[tp].y);
    std::sort(p+1,p+1+t);
#define gn {x.t=x.c==0?0.5*(p[x.y].y-p[x.x].y):x.c==1?0.5*(p[x.y].x-p[x.x].x):p[x.y].y-p[x.x].y;q.push(x);}
    for(H x;!q.empty();)
    if(x=q.top(),q.pop(),(tv[x.x]==0||tv[x.x]==x.t)&&(tv[x.y]==0||tv[x.y]==x.t))tv[x.x]=tv[x.y]=x.t,del[x.x]=del[x.y]=1;
    else if(tv[x.x]!=0&&tv[x.x]!=x.t){while(x.x=pr[x.c][x.x],del[x.x]);if(x.x)gn;}
    else if(tv[x.y]!=0&&tv[x.y]!=x.t){while(x.y=pr[x.c][x.y],del[x.y]);if(x.y)gn;}
    for(ri i=1,to;i<=t;i++)
    if(to=tv[i],p[i].c==0){if(tv[i]==0)to=m;else to+=p[i].y;ar(p[i].x-1,p[i].x,p[i].y-1,to);}
    else if(p[i].c==1){if(tv[i]==0)to=1;else to=p[i].x-to;ar(to-1,p[i].x,p[i].y-1,p[i].y);}
    else if(p[i].c==2){if(tv[i]==0)to=1;else to=p[i].y-to;ar(p[i].x-1,p[i].x,to-1,p[i].y);}
    else{if(tv[i]==0)to=n;else to+=p[i].x;ar(p[i].x-1,to,p[i].y-1,p[i].y);}
    std::sort(dy+1,dy+1+ht),ht=std::unique(dy+1,dy+1+ht)-dy-1,std::sort(d+1,d+1+ct),bt(1,1,ht);
    for(ri i=1;i<=ct;i++)up(1,d[i].l,d[i].r,d[i].p),ans+=1LL*ln[1]*(d[i+1].x-d[i].x);printf("%lld\n",ans);
}
  评论这张
 
阅读(523)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018