Instantly share code, notes, and snippets.

# dohatsutsu/test.cpp Created Dec 21, 2016

 #include using namespace std; typedef pair P; int h,w,n; int ax,ay,bx,by; struct segtree{ bool check(set< P > &T,int a,int b){ set

:: iterator it; it=T.lower_bound(P(a,a)); if(it!=T.end()&&it->first <= b)return true; if(it!=T.begin()&&a<=(--it)->second)return true; return false; } void insert(set

&T,int a,int b){ set

:: iterator it; while(1){ it=T.lower_bound(P(a,a)); if(it!=T.end()&&it->first<=b){ a=min(a,it->first); b=max(b,it->second); T.erase(it); }else if(it!=T.begin()&&a<=(--it)->second){ a=min(a,it->first); b=max(b,it->second); T.erase(it); }else break; } T.insert(P(a,b)); } set< P > t[(1<<18)],u[(1<<18)]; void init(){ for(int i=0;i<(1<<18);i++)t[i].clear(),u[i].clear(); } bool check(int a,int b,int c,int d,int k,int l,int r){ if(b<=l||r<=a)return false; if(check(t[k],c,d))return true; if(a<=l&&r<=b)return check(u[k],c,d); int m=(l+r)/2; return check(a,b,c,d,k*2+1,l,m)||check(a,b,c,d,k*2+2,m,r); } void insert(int a,int b,int c,int d,int k,int l,int r){ if(b<=l||r<=a)return; if(a<=l&&r<=b){insert(t[k],c,d);return;} insert(u[k],c,d); int m=(l+r)/2; insert(a,b,c,d,k*2+1,l,m); insert(a,b,c,d,k*2+2,m,r); } }; segtree T; int main(){ scanf("%d %d %d",&w,&h,&n); long long sum=0; for(int i=0;i