PKU 1974 The Happy Worm

http://poj.org/problem?id=1974
m*nの長方形の空間にk個の石がある。
この時、ある芋虫は縦又は横に可能な限り伸び切るように横たわる。
芋虫は石のあるマスや、長方形の外以外は伸びることが出来る時、何通りの芋虫の配置があるかを答えろというような問題。

半月ぶりのPKU。
入力がかなり多いようなので、vectorとかを使って結構TLEをもらいました。
石の座標と番兵をpairの配列に突っ込んで、全体をソートする方針で解きました。

PI in[1000000];

void solv(){
  int m,n,k;
  scanf("%d%d%d",&m,&n,&k);
  
  rep(i,k){
    int x,y;
    scanf("%d%d",&x,&y);
    --x,--y;
    in[i]=mp(x,y);
  }
  int ans=0;
  rep(i,m){
    in[k+2*i]=mp(i,-1);
    in[k+2*i+1]=mp(i,n);
  }
  
  rep(i,n){
    in[k+2*m+2*i]=mp(-1,i);
    in[k+2*m+2*i+1]=mp(m,i);
  }
  rep(t,2){
    sort(in,in+2*m+2*n+k);
    rep(i,2*m+2*n+k-1){
      if(in[i].F==in[i+1].F && in[i].S+2<in[i+1].S)++ans;
      swap(in[i].F,in[i].S);
    }
    swap(in[2*m+2*n+k-1].F,in[2*m+2*n+k-1].S);
  }
  printf("%d\n",ans);
}

main(){
  int t;
  scanf("%d",&t);
  rep(i,t)solv();
}