Number of special tuples

Revision en2, by MS1908, 2019-08-31 17:07:44

I'm trying to solve the following problem from Hanoi Olympiad in Informatics.

Problem: Given arrays $$$A$$$ $$$a_1,a_2,\ldots, a_m$$$ and $$$B$$$ $$$b_1,b_2,\ldots, b_n$$$. From $$$A$$$ we take $$$a_j, a_k$$$ and from $$$B$$$ we take $$$b_i$$$ such that the tuple formed by these numbers satisfies $$$a_j < b_i < a_k$$$ or $$$a_k < b_i < a_j$$$. Such triple is called special. These numbers will be remove from the original arrays, and we repeat the process with the remaining numbers of the arrays. Find the maximum number of special triples.

Input: First line contains $$$m, n$$$ ($$$2\le m\le 10^5, 2\le n\le 10^5$$$). The second line contains $$$a_1,a_2,\ldots, a_m$$$ ($$$1\le a_i\le 10^9$$$) and the third line contains $$$b_1,b_2,\ldots, b_n$$$ ($$$1\le b_i\le 10^9$$$).

Output: Maximum number of special triples.

**Example: **

Input:

5 3

5 1 3 2 2

2 4 3

Output:

2

Explanation: We can choose $$$a_1=5$$$, $$$a_4=2$$$, $$$b_2=4$$$ and $$$a_2=1$$$, $$$a_3=3$$$, $$$b_1=2$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MS1908 2019-08-31 17:07:44 14
en1 English MS1908 2019-08-31 17:07:15 948 Initial revision (published)