[yLOI2023] 腐草为萤

夜幕降临，在树林中的一条平直的小径上，萤火虫们受到夜晚的呼唤，纷纷外出行动。 将小径视作数轴，一开始，共计 $n$ 只萤火虫在数轴的一些整点上，从左到右依次标号为 $1 \sim n$，第 $i$ 只萤火虫的初始坐标为 $x_i$。每个萤火虫有不同的亮度值，$i$ 号萤火虫的亮度为 $a_i$。 在任意时刻，对任意存活的萤火虫 $i$，它会按如下规则飞行： - 在当前仍存活的萤火虫中，找到与 $i$ 相邻的萤火虫（可能是一只或两只）中亮度最大的一只，记其编号为 $j$。如果 $a_i < a_j$，则 $i$ 会朝着 $j$ 飞行，否则 $i$ 留在原地。 - 这里两只萤火虫『相邻』的定义是：若两只萤火虫之间不存在任何仍存活的萤火虫，则它们相邻。 - 萤火虫飞行的速度均为每秒一个单位长度。 萤火虫生命短暂，当两只萤火虫相遇之时（即两个萤火虫的坐标相同时），亮度值较低的萤火虫将耗尽生命，在小径上消失。显然，最后只会剩余 $1$ 只萤火虫。对其余的每只萤火虫，请分别求出它们耗尽生命时的坐标。 ## Input 第一行是一个整数，表示萤火虫数量 $n$。 第二行有 $n$ 个整数，第 $i$ 个整数表示标号为 $i$ 的萤火虫初始坐标 $x_i$。数据保证 $x_i$ 单调递增。 第三行有 $n$ 个整数，第 $i$ 个整数表示标号为 $i$ 的萤火虫的亮度值 $a_i$。数据保证亮度值互不相同。 ## Output 输出一行 $n$ 个以单个空格隔开的整数，第 $i$ 个整数表示编号为 $i$ 的萤火虫生命耗尽时的坐标。如果 $i$ 号萤火虫最后存活下来了，则第 $i$ 个数输出 0。 [samples] ## Background > 于盛夏之末，入夜仍灼热。 > 又一场离合，开始凄恻。 > 是扇底闪躲，或雨水摧折。 > 哪里都值得，恋恋不舍。 ——银临《腐草为萤》 ## Note ### 样例 1 解释 - 在第一秒时，标号为 $1$ 的萤火虫向右移动，标号为 $2$ 的萤火虫位置不变，标号为 $3$ 的萤火虫向右移动，标号为 $4$ 的萤火虫位置不变。 - 第二秒开始时，萤火虫 $1$ 遇到萤火虫 $2$，前者亮度更低，耗尽生命，此时其坐标为 $2$；萤火虫 $3$ 遇到萤火虫 $4$，前者亮度更低，耗尽生命，此时其坐标为 $4$。 - 接下来，萤火虫 $2$ 向右移动，直到在坐标 $4$ 遇到萤火虫 $4$，耗尽生命。 ### 数据规模与约定 - 对于 $5\%$ 的数据，$n = 2$。 - 对于 $30\%$ 的数据，$n \leq 100$，$x_i \leq 200$。 - 对于 $60\%$ 的数据，$n \leq 10^3$。 - 另有 $5\%$ 的数据，满足特殊约定 A。 - 另有 $5\%$ 的数据，满足特殊约定 B。 - 对 $100\%$ 的数据，保证 $2 \leq n \leq 5 \times 10^5$，$1 \leq x_i \leq 10^9$，$1 \leq a_i \leq n$。且 $x_i < x_{i + 1}$，$a_i$ 是长度为 $n$ 的排列。 其中： - 特殊约定 A：数列 $a$ 单调递增。 - 特殊约定 B：数列 $a$ 是单峰的，仅有一个极大值。即：存在 $p$ 满足 $1 \leq p < n$，使得 $a_1 \sim a_p$ 单调递增，$a_p \sim a_n$ 单调递减. ### 提示 - **请注意大量数据的读入输出对程序效率造成的影响，选择合适的读入输出方式，避免超时**。 - **请注意时间复杂度的常数因子对程序运行效率造成的影响**。 ### 说明 本题共有 7 个附加样例文件，见题目附件中的 glowworm.zip。