K-th element P63584

Using the definitions

implement a function

to return the k-th global element (starting at one) of the elements in the vector of vectors V. Let n = V.size(). For every 0 ≤ i < n, V[i] is sorted increasingly. Furthermore, there are no repeated elements in V.

For exemple, if k = 5, n = 3, and the three vectors are

|| V[0]

V[1]

V[2]

||

then the answer is 2, which is the fifth smallest element inside all the vectors.

Let m = ∑₀ⁿ⁻¹ V[i].size(). Assume that k is between 1 and m, that n is between 2 and 500, and that some V[i] can be empty. If needed, you can implement auxiliar procedures. Take into account that, for the “large” test cases, k = Θ(n) and m = Θ(n²). The expected solution in this cas has cost Θ(n logn).

Observation You only need to submit the required procedure; your main program will be ignored.