Larry's Shoes

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.5s
Python 3.0s
Memory limit: 256M

Problem types

MCPT has decided to give shoes to all of its execs. They have N+1 pairs of shoes, the i^{th} shoe with size a_i, which they plan to give to the N execs and the dictator, Larry.

Each exec has a shoe size b_i. When an exec with shoe size x wears a shoe of size y, their comfort is max(y-x,0).

Since Larry is a dictator, he gets the first choice for his pair of shoes. Once Larry has chosen a pair of shoes, he wants to distribute the rest of the shoes among the execs such that the maximum comfort over execs is minimal (because he's a dictator).

Larry is indecisive however, and doesn't know which pair of shoes he wants to pick. Thus, he wants to know the minimum maximum comfort across all execs if he chooses the i^{th} shoe for 1 \leq i \leq N+1.

Input Specification

The first line will contain one integer N\ (1 \leq N \leq 2\cdot 10^5)

The next line will contain N+1 integers a_i\ (1 \leq a_i \leq 10^9).

The last line will contain N integers b_i\ (1 \leq b_i \leq 10^9).

Output Specification

On one line, you are to output N+1 integers, the i^{th} integer being the minimum maximum comfort if Larry chooses the i^{th} shoe.


Subtask 1 (2%)

N \leq 10

Subtask 2 (9%)

N \leq 2000

Subtask 3 (89%)

No additional constraints.

Sample Input

4 3 7 6
2 6 4

Sample Output

2 2 1 1


There are no comments at the moment.