CSAcademy Beta Round #8 : D. Strange Distance

CSA初参加。割と順調でいきなり赤文字になった。
https://csacademy.com/contest/beta-round-8/#task/strange-distance

問題

２次元座標上でN個の格子点の座標が与えられる。
２頂点(x1,y1)-(x2,y2)の距離をmin(|x1-x2|,|y1-y2|)で定義する。
２頂点間の距離N*(N-1)/2通りを昇順に並べたとき、K番目はいくつか。

解法

二分探索で解く。
頂点をX座標昇順でソートしておこう。
距離がd以下の頂点対の数を列挙していく。

bitを使いながら、頂点番号の大きい順に処理する。
i番目の頂点を処理するとき、尺取法の要領でX[i]+d＜X[j]となるjに対しY座標に対応するbitのエントリをインクリメントしていこう。
(i+1)～(j-1)番の頂点はX座標がd以下なので、条件を満たす頂点対となる。
j以降の頂点については、Y座標が(Y[i]-d)～(Y[i]+d)の範囲の頂点が条件を満たすので、bitで数え上げればよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
};

int N;
ll K;
pair<int,int> P[101010];
BIT<ll,21> bit;

ll num(int v) {
	ZERO(bit.bit);
	ZERO(bit.val);
	
	ll ret=0;
	int i,j=N-1;
	for(i=N-1;i>=0;i--) {
		while(P[j].first>P[i].first+v) bit.add(P[j].second,1),j--;
		ret += j-i;
		ret += bit.total(min(100000,P[i].second+v))-bit.total(max(0,P[i].second-v-1));
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	
	int ret=0;
	for(i=19;i>=0;i--) if(num(ret+(1<<i))<K) ret+=1<<i;
	cout<<ret+1<<endl;
	
}

まとめ

ページ表示後、読み込み終わるまで真っ白な画面が出るのはやめてほしい…。