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; } }