kojingharangの日記

Codeforces #153 Div1 A - Points on Line

12:44 |

• X座標が N 個与えられるので、点間の最大距離が D 以下になるような 3 点の取り方の数を求める問題。
• N≦10**5, D≦10**9

• 両端が決まるとそれに挟まれる別の点の個数だけ 3 点とれる
• ソートしておくと...
• 左端それぞれについて(O(N)), それに対応する右端のうち一番右のところは upper_bound で O(logN) で見つかる
• 右端としてありうるのはX[左端+2]からX[右端]までなので
• ある左端についての答えは M=左端と一番右の右端に挟まれる数字の個数として M≧0 なら 1からMまでの和
• 全体で O(NlogN)

• （あとで）しゃくとり法みたいにすると upper_bound 使わなくてよいようです

• ↓Accepted

int main() {
	//ios::sync_with_stdio(false);
	ll N, D;
	while(cin>>N>>D) {
		VI w(N);
		REP(i, N) {
			cin>>w[i];
		}
		sort(ALL(w));
		
		ll ans=0;
		REP(i, N-2) {
			// binary search [i+1, N-1]
			int idx = (upper_bound(&w[i+1], &w[N], w[i]+D) - &w[0])-1;
			//cout<<i<<" "<<idx<<endl;
			ll mid = idx-i-1;
			if(mid>=0) ans += mid*(mid+1)/2;
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする