// lane_as2_2001 / v1_bisect.cpp
// SIMPLEST PROVABLY-CORRECT version of 2001 "元旦激光炮·改".
// k-th smallest of three sorted read-only arrays.
// Algorithm: bisect the VALUE range; count(x) = sum of upper_bound(x) over the three arrays.
// The smallest value v with count(v) >= k IS the k-th smallest (count is a step function that
// jumps only at values present in the arrays).
// ~30 value steps, each 3 binary searches of ~24 index steps.
static inline int ub_ge(const int *x, int n, int v) {
// number of elements <= v (== upper_bound index)
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + ((hi - lo) >> 1);
if (x[mid] <= v) lo = mid + 1; else hi = mid;
}
return lo;
}
int query_kth(const int *a, int n_a, const int *b, int n_b, const int *c, int n_c, int k)
{
int lo = 1, hi = 1000000000;
while (lo < hi) {
int mid = lo + ((hi - lo) >> 1);
int cnt = ub_ge(a, n_a, mid) + ub_ge(b, n_b, mid) + ub_ge(c, n_c, mid);
if (cnt >= k) hi = mid; else lo = mid + 1;
}
return lo;
}