P15569 [CodeChef] PBATTLE
提高-
题目描述

There are N Pokemon trainers numbered from 1 to N. Each trainer has one Pokemon. All the trainers have arrived to participate in a contest.
There are two battle arenas, one in ground and other in water. Each Pokemon may have different power in both the arenas.
When two Pokemon fight in an arena, the Pokemon having higher power in that arena wins. It is guaranteed that all Pokemon have distinct powers in the same arena to avoid any ties.

The strength of a Pokemon trainer is determined to be the number of other Pokemon his Pokemon can defeat in at least one arena.

It is known that only the Pokemon trainers with the highest strength will qualify for the next round (multiple trainers may have the same strength). Find the number of Pokemon trainers who will qualify for the next round.

------ Input Format ------

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of three lines of input.
  • The first line of each test case contains a single integer N, denoting the number of Pokemon trainers.
  • The second line will contain $N space-separated integers, A_{1},A_{2},\ldots,A_{N}$, where A_{i} denotes the power of the Pokemon of i^{th} trainer in the ground arena.
  • The third line will contain $N space-separated integers, B_{1},B_{2},\ldots,B_{N}$, where B_{i} denotes the power of the Pokemon of i^{th} trainer in the water arena.

------ Output Format ------

For each test case, output on a new line the number Pokemon trainers who will qualify for the next round.

------ Constraints ------

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$
- The elements of array $A$ are distinct.
- The elements of array $B$ are distinct.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------
4
2
1 2
3 4
2
1 2
2 1
3
1 2 3
1 4 2
5
2 3 5 4 1
4 2 1 5 6
----- Sample Output 1 ------
1
2
2
3
----- explanation 1 ------
Test case 1: The second trainer's Pokemon can defeat the first trainer's Pokemon in both arenas so his strength is $1$. Similarly, the first trainer's Pokemon can not defeat the second trainer's Pokemon in any arena so his strength will be $0$. Hence, only the second trainer will qualify.

Test case 2: The second trainer's Pokemon can defeat the first trainer's Pokemon in ground arena so his strength is $1$ and the first trainer's Pokemon can defeat the second trainer's Pokemon in water arena so his strength will also be $1$. Hence both of them will qualify.

Test case 4: The maximum strength possible is $4$. There are $3$ trainers with strength $4$:
- Trainer $3$: Trainer $3$'s pokemon has ground power equal to $5$, so, it can defeat all other $4$ pokemons in the ground arena. Thus, the trainer's strength is $4$.
- Trainer $4$: Trainer $4$'s pokemon has ground power equal to $4$. It can beat the pokemons having ground power less than $4$. These belong to trainers $1, 2,$ and $5$. Similarly, it has water power equal to $5$. Thus, it can also beat trainer $3$'s pokemon which has water power $1$. Thus, total strength of this trainer is $4$.
- Trainer $5$: Trainer $5$'s pokemon has water power equal to $6$, so, it can defeat all other $4$ pokemons in the water arena. Thus, the trainer's strength is $4$.

输入格式

见题面

输出格式

见题面

样例输入
4 2 1 2 3 4 2 1 2 2 1 3 1 2 3 1 4 2 5 2 3 5 4 1 4 2 1 5 6
样例输出
1 2 2 3