1195 - Eat or Be Eaten
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 133
Solved: 57
- Description
Deep down under the sea, there're two kinds of living organism, let's say A and B. A is B's predator, but A will only eat B if and only if its size is strictly bigger than its prey. For example, let the size of A = {8, 1, 7, 3, 1} and B = {3, 6, 1}, then there are 7 pairs of A - B where A > B: 8 - 3, 8 - 6, 8 - 1, 7 - 3, 7 - 6, 7 - 1, 3 - 1.
Given the size of each organism in A and B, write a program to count how many pair of A - B are there such that A is strictly bigger than B. Your program should be efficient as the number of organism may be large.
- Input
- The first line of input contains an integer T, the number of test cases follow.
Each case will begin with two integers N (1 <= N <= 20,000) and M (1 <= M <= 20,000), denoting the number of organism A and B respectively. The next line will contain N positive integers represent the size of each A organism. The third line will contain M positive integers represent the size of each B organism.
- Output
- For each case, print on a single line the number of pair A - B such that A is strictly larger than B.
- sample input
-
2 5 3 8 1 7 3 1 3 6 1 3 4 2 13 7 103 11 290 215
- sample output
-
7 1
- hint
- source