| 记录编号 |
160980 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[APIO2012] 苦无 |
最终得分 |
100 |
| 用户昵称 |
 ztx |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
14.617 s |
| 提交时间 |
2015-04-30 12:36:52 |
内存使用 |
92.10 MiB |
显示代码纯文本
/****************************************\
* Author : ztx
* Title :
[cogs] 798. [APIO2012] 苦无
[bzoj] 2810: [Apio2012]kunai
* ALG : 扫描线+平衡树
* CMT :
6种相撞方式,维护12个set .....
得到一些三角形去掉斜边和一些线段
再求这些线段的长度并
* Time :
\****************************************/
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = getchar() ;
while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
while (ret=getchar() , ret<'!') ;
while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
ret[0]=0;while (CH=getchar() , CH<'!') ;
while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
}
#include <algorithm>
#define maxn 100010LL
struct kunai {
int x,y,d,del,pre[6],suc[6];
} p[maxn] ;
int pp[maxn] ;
/* 四种排序方式 */
inline bool cmp1(const int&a,const int&b) { return p[a].y==p[b].y?p[a].x<p[b].x:p[a].y<p[b].y; }
/* 使得同列相邻 */
inline bool cmp2(const int&a,const int&b) { return p[a].x==p[b].x?p[a].y<p[b].y:p[a].x<p[b].x; }
/* 使得同行相邻 */
inline bool cmp3(const int&a,const int&b) { return (p[a].x-p[a].y==p[b].x-p[b].y)?(p[a].x<p[b].x):(p[a].x-p[a].y<p[b].x-p[b].y); }
/* 使得主对角线相邻 */
inline bool cmp4(const int&a,const int&b) { return (p[a].x+p[a].y==p[b].x+p[b].y)?(p[a].x<p[b].x):(p[a].x+p[a].y<p[b].x+p[b].y); }
/* 使得副对角线相邻 */
struct Collide {
int a,b,tim;
bool operator < (const Collide&b) const { return tim<b.tim; }
}sta[maxn<<1]; int top;
int sta2[maxn<<1],top2;
#undef maxn
#define right 0LL
#define up 1LL
#define left 2LL
#define down 3LL
inline bool Judge1(int a,int b) {
/* 列相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d) return false ;
if (p[a].y!=p[b].y) return false ;
if (p[a].d==right || p[a].d==left || p[b].d==right || p[b].d==left) return false ;
if (p[a].d==down) return p[a].x<p[b].x ; else return p[a].x>p[b].x ;
}
inline bool Judge2(int a,int b) {
/* 行相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d) return false ;
if (p[a].x!=p[b].x) return false ;
if (p[a].d==up || p[a].d==down || p[b].d==up || p[b].d==down) return false ;
if (p[a].d==right) return p[a].y<p[b].y ; else return p[a].y>p[b].y ;
}
inline bool Judge3(int a,int b) {
/* 主对角线右上相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d || p[a].x==p[b].x) return false ;
if (p[a].x-p[a].y != p[b].x-p[b].y) return false ;
if (p[a].d==left || p[a].d==down || p[b].d==left || p[b].d==down) return false ;
if (p[a].d==right) return p[a].x<p[b].x ; else return p[a].x>p[b].x ;
}
inline bool Judge4(int a,int b) {
/* 主对角线左下相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d || p[a].x==p[b].x) return false ;
if (p[a].x-p[a].y != p[b].x-p[b].y) return false ;
if (p[a].d==right || p[a].d==up || p[b].d==right || p[b].d==up) return false ;
if (p[a].d==down) return p[a].x<p[b].x ; else return p[a].x>p[b].x ;
}
inline bool Judge5(int a,int b) {
/* 副对角线左上相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d || p[a].x==p[b].x) return false ;
if (p[a].x+p[a].y != p[b].x+p[b].y) return false ;
if (p[a].d==right || p[a].d==down || p[b].d==right || p[b].d==down) return false ;
if (p[a].d==left) return p[a].x<p[b].x ; else return p[a].x>p[b].x ;
}
inline bool Judge6(int a,int b) {
/* 副对角线右下相撞 */
if (a==b || p[a].del || p[b].del || p[a].d==p[b].d || p[a].x==p[b].x) return false ;
if (p[a].x+p[a].y != p[b].x+p[b].y) return false ;
if (p[a].d==left || p[a].d==up || p[b].d==left || p[b].d==up) return false ;
if (p[a].d==down) return p[a].x<p[b].x ; else return p[a].x>p[b].x ;
}
struct HEAP {
#define size 5000010LL
Collide a[size] ;
int tott ;
inline void init() { tott = 0 ; }
inline void Exchange(Collide&a,Collide&b){Collide c=a;a=b;b=c;}
inline void Up(int x) { for (;x>1&&a[x]<a[x>>1];Exchange(a[x],a[x>>1]),x>>=1) ; }
inline void Down(int x) {
int y ;
while (y=x<<1, y<=tott) {
if (y<tott && a[y+1]<a[y]) y++ ;
if (a[y]<a[x]) Exchange(a[x],a[y]) , x=y;
else break ;
}
}
inline int abss(int x) { return x<0?-x:x; }
inline int dist(int a,int b) { return abss(p[a].x-p[b].x)+abss(p[a].y-p[b].y); }
inline void insert(int x,int y) {
// printf("Insert %d & %d\n",x,y);
a[++tott]=(Collide){x,y,dist(x,y)}; Up(tott) ; }
inline Collide top() { return a[1] ; }
inline void pop() { Exchange(a[1],a[tott--]); Down(1) ; }
inline bool Top_Invalid() { return p[a[1].a].del||p[a[1].b].del; }
inline bool empty() { while(tott&&Top_Invalid())pop();return tott==0; }
#undef size
} heap ;
int R , C , n ;
namespace sbsbsb {
#define maxn 1000010LL
#define M (L+R>>1)
#define l(o) o<<1
#define r(o) o<<1|1
#define lc l(o),L,M
#define rc r(o),M+1,R
struct NODE {
int cov , x1 , x2 , y ;
bool operator < (const NODE& b) const { return y < b.y ; }
} line[maxn] ;
int tot,cnt[maxn],x[maxn],s[maxn] ;
void update(int o,int L,int R) {
if (cnt[o]) s[o]=x[R+1]-x[L] ;
else if (L == R) s[o] = 0 ;
else s[o] = s[l(o)]+s[r(o)] ;
}
void insert(int o,int L,int R,int S,int T,int V) {
if (S<=L && R<=T) { cnt[o]+=V,update(o,L,R);return; }
if (T <= M) insert(lc,S,T,V) ;
else if (S > M) insert(rc,S,T,V) ;
else insert(lc,S,M,V) , insert(rc,M+1,T,V) ;
update(o,L,R) ;
}
void AddLine(int x1,int y1,int x2,int y2) {
// printf("AddLine (%d,%d)->(%d,%d) tot = %d\n",x1,y1,x2,y2,tot);
line[++tot]=(NODE){ 1,x1,x2,y1},x[tot]=x1;
line[++tot]=(NODE){-1,x1,x2,y2},x[tot]=x2;
}
void init() { tot = 0 ; }
ll work() {
int top=1,i,L,R;
ll ans=0;
std::sort(x+1,x+tot+1),std::sort(line+1,line+tot+1);
Rep (i,2,tot) if (x[i]!=x[i-1]) x[++top]=x[i] ;
Rep (i,1,tot) {
if (i>1) ans+=(ll)s[1]*(line[i].y-line[i-1].y);
L=std::lower_bound(x+1,x+top+1,line[i].x1)-x;
R=std::lower_bound(x+1,x+top+1,line[i].x2)-x-1;
insert(1,1,top,L,R,line[i].cov) ;
}
return ans ;
}
#undef maxn
#undef M
#undef lc
#undef rc
#undef l
#undef r
}
int main() {
int i,p_up,p_down,p_left,p_right,p_last1,p_last2;
#define READ
#ifdef READ
freopen("kunai.in" ,"r",stdin ) ;
freopen("kunai.out","w",stdout) ;
#endif
read(C),read(R) ;
read(n) ;
#define dir p[i].d
Rep (i,1,n)
read(p[i].y),read(p[i].x),read(p[i].d),pp[i]=i;
#undef dir
#define dir p[pp[i]].d
/* 初始化撞击事件,对每一种相撞方式做一个链表 */
/* 类型1,同列 */
p[0].del = 1 ; heap.init() ;
std::sort(pp+1,pp+n+1,cmp1) ;
p_up=0,p_down=0,p_last1=0;
Rep (i,1,n) {
if (dir==left || dir==right) continue ;
if (dir==down) p_down=pp[i];
if (dir==up) p_up=pp[i];
/* 因为纵坐标从小到大,p_down要么不与i同列,要么在下方 */
if (Judge1(p_up,p_down))
heap.insert(p_up,p_down) ;
if (p_last1 && p[p_last1].y==p[pp[i]].y)
p[pp[i]].pre[0] = p_last1 , p[p_last1].suc[0] = pp[i] ;
p_last1 = pp[i] ;
}
/* 类型2,同行 */
std::sort(pp+1,pp+n+1,cmp2) ;
p_left=0,p_right=0,p_last1=0;
Rep (i,1,n) {
if (dir==up || dir==down) continue ;
if (dir==right) p_right=pp[i];
if (dir==left) p_left=pp[i];
/* 因为横坐标从小到大,p_left要么不与i同行,要么在左方 */
if (Judge2(p_left,p_right))
heap.insert(p_left,p_right) ;
if (p_last1 && p[p_last1].x==p[pp[i]].x)
p[pp[i]].pre[1] = p_last1 , p[p_last1].suc[1] = pp[i] ;
p_last1 = pp[i] ;
}
/* 类型3,4,主对角线 */
std::sort(pp+1,pp+n+1,cmp3) ;
p_up=p_left=p_right=p_down=p_last1=p_last2=0;
Rep (i,1,n) {
/* 在同一对角线上x递增 */
if (dir==right || dir==up) {
if (dir==right) p_right=pp[i];
if (dir==up) p_up=pp[i];
if (Judge3(p_up,p_right))
heap.insert(p_up,p_right) ;
if (p_last1 && p[p_last1].x-p[p_last1].y==p[pp[i]].x-p[pp[i]].y)
p[pp[i]].pre[2] = p_last1 , p[p_last1].suc[2] = pp[i] ;
p_last1 = pp[i] ;
} else {
if (dir==down) p_down=pp[i];
if (dir==left) p_left=pp[i];
if (Judge4(p_left,p_down))
heap.insert(p_left,p_down) ;
if (p_last2 && p[p_last2].x-p[p_last2].y==p[pp[i]].x-p[pp[i]].y)
p[pp[i]].pre[3] = p_last2 , p[p_last2].suc[3] = pp[i] ;
p_last2 = pp[i] ;
}
}
/* 类型5,6,副对角线 */
std::sort(pp+1,pp+n+1,cmp4) ;
p_up=p_left=p_right=p_down=p_last1=p_last2=0;
Rep (i,1,n) {
/* 在同一对角线上x递增 */
if (dir==left || dir==up) {
if (dir==left) p_left=pp[i];
if (dir==up) p_up=pp[i];
if (Judge5(p_up,p_left))
heap.insert(p_up,p_left) ;
if (p_last1 && p[p_last1].x+p[p_last1].y==p[pp[i]].x+p[pp[i]].y)
p[pp[i]].pre[4] = p_last1 , p[p_last1].suc[4] = pp[i] ;
p_last1 = pp[i] ;
} else {
if (dir==down) p_down=pp[i];
if (dir==right) p_right=pp[i];
if (Judge6(p_right,p_down))
heap.insert(p_right,p_down);
if (p_last2 && p[p_last2].x+p[p_last2].y==p[pp[i]].x+p[pp[i]].y)
p[pp[i]].pre[5] = p_last2 , p[p_last2].suc[5] = pp[i] ;
p_last2 = pp[i] ;
}
}
#undef dir
// puts("\n\nBegin Collide ...............\n") ;
// printf("heap_size = %d\n",heap.tott);
int timnow,top,u,j;
while (!heap.empty()) {
timnow = heap.top().tim ;
// printf("time now = %d\n",timnow) ;
sta[top=1]=heap.top();
heap.pop() ;
while (!heap.empty() && heap.top().tim==timnow) sta[++top]=heap.top(),heap.pop();
top2=0;
Rep (i,1,top) {
// printf("Collide %d with %d\n",sta[i].a,sta[i].b);
if (!p[sta[i].a].del) sta2[++top2]=sta[i].a,p[sta[i].a].del=timnow;
if (!p[sta[i].b].del) sta2[++top2]=sta[i].b,p[sta[i].b].del=timnow;
}
Rep (i,1,top2) {
u=sta2[i];
// printf("finding %d\n",u);
rep (j,0,6) {
int pre=p[u].pre[j],suc=p[u].suc[j];
while (pre && p[pre].del) pre=p[pre].pre[j];
while (suc && p[suc].del) suc=p[suc].suc[j];
p[suc].pre[j]=pre;
p[pre].suc[j]=suc;
if (pre && suc) {
if (j==0 && Judge1(pre,suc))heap.insert(pre,suc);
if (j==1 && Judge2(pre,suc))heap.insert(pre,suc);
if (j==2 && Judge3(pre,suc))heap.insert(pre,suc);
if (j==3 && Judge4(pre,suc))heap.insert(pre,suc);
if (j==4 && Judge5(pre,suc))heap.insert(pre,suc);
if (j==5 && Judge6(pre,suc))heap.insert(pre,suc);
}
}
}
}
Rep (i,1,n) {
if (!p[i].del) {
if (p[i].d==right)p[i].del=C-p[i].y;
if (p[i].d== up)p[i].del=p[i].x-1;
if (p[i].d== left)p[i].del=p[i].y-1;
if (p[i].d== down)p[i].del=R-p[i].x;
} else p[i].del >>= 1 ;
// printf("i=%d del=%d dir=%d , time %d\n",i,(bool)p[i].del,p[i].d,p[i].del);
}
// puts("\n\nGet area.....................\n");
sbsbsb::init() ;
#define dir p[i].d
#define x p[i].x
#define y p[i].y
#define del p[i].del
#define Add_Line(a,b,c,d) sbsbsb::AddLine(a,b,c,d)
Rep (i,1,n) {
if (dir== up) Add_Line(x-del,y,x+1,y+1) ;
if (dir== down) Add_Line(x,y,x+del+1,y+1) ;
if (dir== left) Add_Line(x,y-del,x+1,y+1) ;
if (dir==right) Add_Line(x,y,x+1,y+del+1) ;
}
#undef dir
#undef x
#undef y
#undef del
printf("%lld\n", sbsbsb::work()) ;
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
getchar() ; getchar() ;
#endif
return 0 ;
}
/*
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
3 3
2
1 2 0
2 1 3
3 3
2
3 2 2
2 3 1
3 3
2
1 2 0
2 3 1
3 3
2
2 1 3
3 2 2
4 4
3
2 1 3
1 2 0
2 3 1
5 5
4
4 1 3
3 2 3
2 3 0
1 4 0
*/