P6877 [JOI 2020 Final] Just Long Neckties

JOI Company invented a kind of necktie. There are $N+1$ neckties in total, numbered from $1$ to $N+1$. The length of the $i$-th necktie is $A_i$. JOI Company held a party. There are $N$ employees at the party. At the beginning, the $j$-th employee was wearing a necktie of length $B_j$. The party proceeds as follows: 1. First, the boss of JOI Company, Mr. JOI, selects one necktie and takes it away. 2. Then, each employee chooses one necktie, making sure that no two employees choose the same necktie. 3. Finally, they take off the neckties they were wearing at first, and put on the chosen neckties. If an employee was initially wearing a necktie of length $b$, and chooses a necktie of length $a$, then the employee feels a weirdness of $\max\{a-b,0\}$. The overall weirdness of the party is the maximum weirdness among all employees. Mr. JOI defines $C_k$ as the minimum possible overall weirdness after he selects the $k$-th necktie. Mr. JOI wants to know the exact value of $C_k$.

The first line contains an integer $N$, representing the number of employees. The second line contains $N+1$ integers $A_i$, representing the length of each necktie. The third line contains $N$ integers $B_j$, representing the length of the necktie each person was wearing at the beginning.

Output one line with $N+1$ integers $C_k$, representing the minimum overall weirdness after selecting each necktie.

#### Explanation for Sample 1 Let us assume that Mr. JOI selects the $4$-th necktie. Then the employees may choose as follows: - Employee $1$ chooses the $1$-st necktie, and feels weirdness $2$. - Employee $2$ chooses the $2$-nd necktie, and feels weirdness $0$. - Employee $3$ chooses the $3$-rd necktie, and feels weirdness $3$. The overall weirdness is $3$. But we can further reduce the overall weirdness: - Employee $1$ chooses the $2$-nd necktie, and feels weirdness $1$. - Employee $2$ chooses the $3$-rd necktie, and feels weirdness $1$. - Employee $3$ chooses the $1$-st necktie, and feels weirdness $0$. The overall weirdness is $1$. Therefore, $C_4=1$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (1 pts): $N \le 10$. - Subtask 2 (8 pts): $N \le 2000$. - Subtask 3 (91 pts): no additional constraints. For $100\%$ of the testdata: - $1 \le N \le 2 \times 10^5$. - $1 \le A_i \le 10^9$. - $1 \le B_j \le 10^9$. #### Notes Translated from [The 19th Japanese Olympiad in Informatics, Final Round](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [A 長いだけのネクタイ](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t1.pdf). Translated by ChatGPT 5