Segment Set - Segment Intersections: Manhattan Geometry - sinapusu2002 @ ウィキ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A
線分の交差数を数える問題。

コード実行速度１８位(配列に変えたら16位になった)
平凡中の平凡（戸愚呂弟の100％中の100％）
構造体を使えば上位の人と争えるけど、実装が長くなるので短時間で実装できるmapとsetを使った。
答えの交点数が多くなれば下位の人と上位の人の分離がもっと明確化するな。

#include<stdio.h>
#include<map>
#include<set>
#include<algorithm>
 
  
struct E{
   int R,count;    
};
  
std::map<int,std::map<int,E> > memo;
std::map<int,std::map<int,int> > hs;
std::map<int,std::set<int> > add,dell;
std::map<int,int> toP;
  
void f1(int deep,int L,int R){
   if(R<L)return;
   E e1;
   e1.R=R;
   e1.count=0;
   memo[deep][L]=e1;
   if(R<=L){
       return ;
   }else{
       int M=(L+R)/2;
       f1(deep+1,L,M);
       f1(deep+1,M+1,R);
   }
}
void addF(int deep,int L,int R,int P,int add){
   if(deep==0){
       P=toP[P];
   }
   E e1=memo[deep][L];
   e1.count+=add;
   memo[deep][L]=e1;
   //printf("(af=L=%d R=%d P=%d d=%d)",L,R,P,deep);
   if(L==R){
       return ;
   }else{
       int M=(L+R)/2;
       if((L<=P)&&(P<=M)){
           addF(deep+1,L,M,P,add);
       }else if((M+1<=P)&&(P<=R)){
           addF(deep+1,M+1,R,P,add);
       }
   }
}
int sumF(int deep,int L,int R,int L1,int R1){
   if(deep==0){
       L1=toP[L1];
       R1=toP[R1];
   }
 
   if(R<L1)return 0;
   if(R1<L)return 0;
   //printf("(sf=%d %d %d)",deep,L,R);
   if(L==R){
       return memo[deep][L].count;
   }
   if((L1<=L)&&(R<=R1)){
       return memo[deep][L].count;
   }else{
       int res=0;
       int M=(L+R)/2;
       res+=sumF(deep+1,L,M,L1,R1);
       res+=sumF(deep+1,M+1,R,L1,R1);
       return res;
   }
}
  
int main(){
   int n;
   scanf("%d",&n);
   for(int i=0;i<n;i++){
       int x1,x2,y1,y2;
       scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
       toP[y1]=0;
       toP[y2]=0;
       if(x1==x2){
           hs[x1][std::min(y1,y2)]=std::max(y1,y2);
       }else{
           add[std::min(x1,x2)].insert(y1);
           dell[std::max(x1,x2)].insert(y1);
       }
   }
   std::map<int,int>::iterator mIt;
   int p=0;
   for(mIt=toP.begin();mIt!=toP.end();mIt++){
       toP[(*mIt).first]=p;
       p++;
   }
   int pSize=toP.size()-1;
   f1(0,0,pSize);
   std::map<int,std::set<int> >::iterator msIt1,msIt2;
   std::map<int,std::map<int,int> >::iterator mmIt1;
   msIt1=add.begin();
   msIt2=dell.begin();
   mmIt1=hs.begin();
   int ans=0;
 
   std::map<int,std::map<int,E> >::iterator mmItT;
 
 
   while(mmIt1!=hs.end()){
       int x=(*mmIt1).first;
       //printf("<%d %d>\n",x,pSize);
 
       while((msIt1!=add.end())&&((*msIt1).first<=x)){
           int x1=(*msIt1).first;
           std::set<int>::iterator sIt;
           for(sIt=add[x1].begin();sIt!=add[x1].end();sIt++){
               addF(0,0,pSize,(*sIt),1);
           }
           msIt1++;
       }
       while((msIt2!=dell.end())&&((*msIt2).first<x)){
           int x2=(*msIt2).first;
           std::set<int>::iterator sIt;
           for(sIt=dell[x2].begin();sIt!=dell[x2].end();sIt++){
               addF(0,0,pSize,(*sIt),-1);
           }
           msIt2++;
       }
 
 
 
       std::map<int,int>::iterator mIt2;
       for(mIt2=hs[x].begin();mIt2!=hs[x].end();mIt2++){
           int L=(*mIt2).first;
           int R=(*mIt2).second;
           ans+=sumF(0,0,pSize,L,R);
       }
       mmIt1++;
   }
   printf("%d\n",ans);
}