K-th of Two Sorted Arrays

Difficulty: 1400 3000 ms 128 MB

two-pointers

Two arrays are already sorted. Print the K-th smallest element of their union (duplicates kept).

Input: the first line has N, M and K; the second line has the N sorted values of A; the third line has the M sorted values of B.

Output: the K-th smallest element of the merged multiset.

Constraints:

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ K ≤ N+M
• −10⁹ ≤ values ≤ 10⁹

Sample Tests

3 3 4
1 3 5
2 4 6

4

1 1 2
5
1

5

Read the Editorial Statistics