PKU 3067 Japan

http://poj.org/problem?id=3067
日本の西と東をいくつかの高速道路で結ぶ。
このとき、高速道路は何箇所交差しているかを答えろというような問題。

愚直にやるとTLEしたので、なんとかBITを思いついたのですがWA。
どうやってもWAが取れなかったので、discussを見てみるとint64とか書いてあって、直したら通りました。
kの上限を書いておいて欲しいと思いました。

int BIT[11000];

int count(int x){
  int ret=0;
  while(x>0){
    ret+=BIT[x];
    x-=(x&-x);
  }
  return ret;
}

void add(int x){
  while(x<=10000){
    ++BIT[x];
    x+=x&-x;
  }
}

PI in[2000000];

main(){
  int T;
  scanf("%d",&T);
  rep(te,T){
    memset(BIT,0,sizeof(BIT));
    int n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    rep(i,k)
      scanf("%d%d",&in[i].F,&in[i].S);
    sort(in,in+k);
    
    rep(i,k){
      ans+=count(2000)-count(in[i].S);
      add(in[i].S);
    }
    cout<<"Test case "<<1+te<<": "<<ans<<endl;
  }
}