代码

#include <algorithm>

int query_kth(const int *A, int na, const int *B, int nb, const int *C, int nc, int k)
{
	const int *value[3] = {A, B, C};
	int l[3] = {0, 0, 0}, r[3] = {na, nb, nc}, mid[3] = {na + 1 >> 1, nb + 1 >> 1, nc + 1 >> 1};
	int size(3), o[3] = {0, 1, 2}, x[3] = {value[0][na + 1 >> 1], value[1][nb + 1 >> 1], value[2][nc + 1 >> 1]};
	while (true)
	{
		if (size == 1 && k == mid[0] + mid[1] + mid[2] + 1)
			return x[*o];
		if (k <= mid[0] + mid[1] + mid[2] + 1)
		{
			std::sort(o, o + size, [&](const int i0, const int i1) { return x[i0] > x[i1]; });
			r[*o] = mid[*o] - 1, mid[*o] = l[*o] + r[*o] + 1 >> 1;
			if (l[*o] <= r[*o])
				x[*o] = value[*o][mid[*o]];
			else
				std::swap(*o, o[--size]);
		}
		else
		{
			std::sort(o, o + size, [&](const int i0, const int i1) { return x[i0] < x[i1]; });
			l[*o] = mid[*o] + 1, mid[*o] = l[*o] + r[*o] + 1 >> 1;
			if (l[*o] <= r[*o])
				x[*o] = value[*o][mid[*o]];
			else
				std::swap(*o, o[--size]);
		}
	}
}

评测结果