Peking University Online Judge 3579 Median

この手の問題を最近よく見るんですけど、もしかしてベタ問の類ですか？
cinで入力するとタイムアウトするのも毎度おなじみ
類題：https://beta.atcoder.jp/contests/abc107/tasks/arc101_b
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0646

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int ll;
static const int MAX_N = 100000;
static const int MAX_X = 1000000000;

int N;
int X[MAX_N];

int main(){
	while(scanf("%d", &N) != EOF){
		for(int i = 0; i < N; i++) scanf("%d", &X[i]);
		sort(X, X + N);
		
		ll num_diff = (ll)N * (ll)(N - 1) / 2LL;
		ll M = (num_diff % 2 == 0 ? num_diff / 2LL + 1LL : (num_diff + 1LL) / 2LL);
		
		int lb = 0, ub = MAX_X + 1;
		while(ub - lb > 1){
			int mid = lb + (ub - lb) / 2;
			ll cnt = 0;
			int j = 0;
			for(int i = 0; i < N; i++){
				for(; j < N && X[j] - X[i] < mid; j++);
				if(X[j] - X[i] >= mid) cnt += (ll)(N - j);
			}
			if(cnt >= M) lb = mid;
			else ub = mid;
		}
		
		printf("%d\n", lb);
	}
	return 0;
}