POJ 2104 K-th Number

例の平方分割で解ける問題

バケットのサイズを色々試してみた。

B = 1100 →　TLE (>20000MS)
B = 1000 →　11735MS
B = 900 →　11782MS
B = 850 →　11829MS
B = 800 →　11157MS
B = 700 →　12235MS

結果B = 800が一番早い（？）

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MN = 100000;
const int B = 800;

int n,m;
int a[MN];
int nums[MN];
vector<int> bucket[MN / B];
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 0;i < n;i++){
		scanf("%d",&a[i]);
		bucket[i / B].push_back(a[i]);
		nums[i] = a[i];
	}
	sort(nums,nums+n);

	for(int i = 0;i < n / B;i++) sort(bucket[i].begin(),bucket[i].end());

	for(int i = 0;i < m;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		l--;
		int lb = -1,ub = n - 1;
		while(ub - lb > 1){
			int md = (lb + ub) / 2;
			int x = nums[md];
			int tl = l,tr = r,c = 0;

			while(tl < tr && tl % B != 0) if(a[tl++] <= x) c++;
			while(tl < tr && tr % B != 0) if(a[--tr] <= x) c++;

			while(tl < tr){
				int b = tl / B;
				c += upper_bound(bucket[b].begin(),bucket[b].end(),x) - bucket[b].begin();
				tl += B;
			}
			if(c >= k) ub = md;
			else lb = md;
		}
		printf("%d\n",nums[ub]);
	}
	return 0;
}