Problem Description

There are $N$ students in the class. Each student is assigned an ID from $0$ to $N - 1$ based on the current class ranking. That is, student $i$ (for all $0 \le i \le N - 1$) currently has class rank $i$. Here, rank $0$ is the best, and rank $N - 1$ is the worst.

The class has recently finished Chinese and Math exams. Student $i$ (for all $0 \le i \le N - 1$) has rank $A[i]$ in the Chinese exam and rank $B[i]$ in the Math exam. Both $A$ and $B$ are permutations of length $N$.

:::info[What is a permutation of length $N$?]{open} In this problem, a permutation $P$ of length $N$ is an array of length $N$ such that for all $0 \le i \le N - 1$, we have $0 \le P[i] \le N - 1$, and for all $0 \le i < j \le N - 1$, we have $P[i] \ne P[j]$.

For example, $[2, 1, 0]$ is a permutation of length $3$, but $[1, 2, 3]$ and $[2, 0, 2]$ are not permutations of length $3$. :::

The teacher wants to re-rank all students. The new ranking can be represented by a permutation $P$.

For each student $i$, their new class rank must satisfy at least one of the following conditions:

• For all $j$ such that $P[j] < P[i]$, student $j$ has a better Chinese score than student $i$ (i.e., $A[j] < A[i]$), or
• For all $j$ such that $P[j] < P[i]$, student $j$ has a better Math score than student $i$ (i.e., $B[j] < B[i]$).

:::warning[Warning]{open} This condition only applies to those $j$ with $P[j] < P[i]$. There are no restrictions for those $j$ with $P[j] \ge P[i]$.

For each student $i$, when checking whether the condition is satisfied, you must first choose one subject, and then compare student $i$ with all the corresponding students $j$ using that subject. For the same $i$, all different $j$ must be better than student $i$ in the same subject. You cannot switch subjects halfway through when evaluating the condition for student $i$. :::

The dissatisfaction of the new class ranking is defined as the maximum amount of rank drop among all students. In other words, dissatisfaction is the maximum value of $P[i] - i$ (for all $0 \le i \le N - 1$).

:::warning[Warning]{open} Dissatisfaction is the maximum of $P[i] - i$. The value of $i - P[i]$ does not affect the calculation of dissatisfaction. :::

Among all possible new rankings, find the minimum possible dissatisfaction.

Implementation Details

You need to implement the following function:

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)

• $N$: the number of students.
• $A$: an array of length $N$, representing the ranks in the Chinese exam.
• $B$: an array of length $N$, representing the ranks in the Math exam.
• This function should return the minimum dissatisfaction of the new class ranking.
• This function is called exactly once for each testdata.

Input Format

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

Output Format

A single integer, which is the return value of minimum_dissatisfaction.

Hint

Sample

Consider the following function call:

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

In this example, one way to assign the new ranking is $P = [0, 2, 3, 4, 1]$.

Consider student $1$, with $P[1] = 2$. All students $j$ such that $P[j] < P[1]$ have a better Math rank than student $1$, so this student satisfies the class ranking condition.

Next, consider student $2$, with $P[2] = 3$. All students $j$ such that $P[j] < P[2]$ have a better Chinese rank than student $2$, so this student also satisfies the class ranking condition.

It can be verified that all other students also satisfy the class ranking condition.

The dissatisfaction of this new ranking is $1$. There is no other new ranking with lower dissatisfaction, so the function should return $1$.

Constraints

• $1 \le N \le 5\ 000\ 000$.
• For all $0 \le i \le N - 1$, $0 \le A[i], B[i] \le N - 1$.
• For all $0 \le i < j \le N - 1$, $A[i] \ne A[j]$.
• For all $0 \le i < j \le N - 1$, $B[i] \ne B[j]$.

Subtasks

1. ($3$ points) $N \le 8$.
2. ($4$ points) $N \le 20$.
3. ($13$ points) $N \le 500$.
4. ($12$ points) $N \le 3000$, and for all $0 \le i \le N - 1$, $A[i] + B[i] = N - 1$.
5. ($19$ points) $N \le 3000$.
6. ($15$ points) $N \le 100\ 000$, and for all $0 \le i \le N - 1$, $A[i] + B[i] = N - 1$.
7. ($17$ points) $N \le 100\ 000$.
8. ($17$ points) no additional constraints.

Note: For subtask $8$, the judging program alone is guaranteed to take $1500$ milliseconds out of the $3000$ milliseconds time limit.

Translated by ChatGPT 5