P9066 [yLOI2023] Rotting Grass Turns Into Fireflies

> At the end of midsummer, the night is still scorching. > Another parting and reunion begins in sorrow. > Is it hiding under a fan, or crushed by rain. > Everywhere is worth it, unwilling to let go. — Yin Lin, *Rotting Grass Turns Into Fireflies*

As night falls, on a straight path in the woods, fireflies respond to the call of the night and go out to move around. Treat the path as a number line. Initially, there are $n$ fireflies located at some integer points on the number line, labeled from left to right as $1 \sim n$. The initial coordinate of firefly $i$ is $x_i$. Each firefly has a different brightness value, and the brightness of firefly $i$ is $a_i$. At any moment, for any surviving firefly $i$, it flies according to the following rules: - Among the fireflies adjacent to $i$ (there may be one or two) that are still alive, find the one with the maximum brightness, and denote its index as $j$. If $a_i < a_j$, then $i$ flies toward $j$; otherwise, $i$ stays in place. - Here, two fireflies are defined to be “adjacent” if there is no other surviving firefly between them. - All fireflies fly at a speed of 1 unit length per second. Fireflies have short lives. When two fireflies meet (i.e., their coordinates become the same), the firefly with the lower brightness will run out of life and disappear from the path. Clearly, in the end only 1 firefly will remain. For each of the other fireflies, find the coordinate where it runs out of life.

The first line contains an integer, representing the number of fireflies $n$. The second line contains $n$ integers, where the $i$-th integer represents the initial coordinate $x_i$ of firefly $i$. The testdata guarantees that $x_i$ is strictly increasing. The third line contains $n$ integers, where the $i$-th integer represents the brightness value $a_i$ of firefly $i$. The testdata guarantees that all brightness values are distinct.

Output one line with $n$ integers separated by single spaces. The $i$-th integer represents the coordinate where firefly $i$ runs out of life. If firefly $i$ survives to the end, output 0 for the $i$-th number.

### Explanation of Sample 1 - In the first second, firefly $1$ moves to the right, firefly $2$ stays still, firefly $3$ moves to the right, and firefly $4$ stays still. - At the beginning of the second second, firefly $1$ meets firefly $2$. The former has lower brightness and runs out of life, and its coordinate is $2$. Firefly $3$ meets firefly $4$. The former has lower brightness and runs out of life, and its coordinate is $4$. - Next, firefly $2$ moves to the right until it meets firefly $4$ at coordinate $4$, and then runs out of life. ### Constraints - For $5\%$ of the testdata, $n = 2$. - For $30\%$ of the testdata, $n \leq 100$, $x_i \leq 200$. - For $60\%$ of the testdata, $n \leq 10^3$. - Another $5\%$ of the testdata satisfies Special Condition A. - Another $5\%$ of the testdata satisfies Special Condition B. - For $100\%$ of the testdata, it is guaranteed that $2 \leq n \leq 5 \times 10^5$, $1 \leq x_i \leq 10^9$, $1 \leq a_i \leq n$. Also, $x_i < x_{i + 1}$, and $a_i$ is a permutation of length $n$. Where: - Special Condition A: the sequence $a$ is strictly increasing. - Special Condition B: the sequence $a$ is unimodal with only one maximum. That is, there exists $p$ satisfying $1 \leq p < n$ such that $a_1 \sim a_p$ is strictly increasing, and $a_p \sim a_n$ is strictly decreasing. ### Notes - **Please note that input and output on large testdata may affect program efficiency. Choose appropriate I/O methods to avoid TLE.** - **Please note that the constant factor in time complexity may affect program running efficiency.** ### Additional Information There are 7 additional sample files for this problem. See glowworm.zip in the attachments. Translated by ChatGPT 5