int query_kth(const int *a, int n_a,
const int *b, int n_b,
const int *c, int n_c, int k)
{
const int inf = 0x7fffffff;
/*
* If d=floor(k/3), take the d-th remaining item of every array.
* The smallest of those three items has at most 3*d-1 items before
* it in the union, hence its first d items can safely be discarded.
*/
while (k > 3) {
const int d = k / 3;
const int va = n_a >= d ? a[d - 1] : inf;
const int vb = n_b >= d ? b[d - 1] : inf;
const int vc = n_c >= d ? c[d - 1] : inf;
if (va <= vb && va <= vc) {
a += d;
n_a -= d;
} else if (vb <= vc) {
b += d;
n_b -= d;
} else {
c += d;
n_c -= d;
}
k -= d;
}
int answer = 0;
do {
const int va = n_a ? *a : inf;
const int vb = n_b ? *b : inf;
const int vc = n_c ? *c : inf;
if (va <= vb && va <= vc) {
answer = va;
++a;
--n_a;
} else if (vb <= vc) {
answer = vb;
++b;
--n_b;
} else {
answer = vc;
++c;
--n_c;
}
} while (--k);
return answer;
}