P14126 [SCCPC 2021] Ants

有 $n$ 只蚂蚁住在一根长度为 $(10^9 + 1)$ 单位的棍子上。第 $i$ 只蚂蚁初始位于距离棍子左端 $a_i$ 单位的位置。部分蚂蚁初始面向左，部分蚂蚁初始面向右。所有蚂蚁都会以 $1$ 单位每秒的速度向自己面朝的方向前进。当两只蚂蚁正面相遇（也就是位于同一点且方向相对）时，它们会立即同时调头继续前进。 棍子的两端分别有一个障碍物，左端和右端各一个。当蚂蚁撞上障碍物时也会立即调头继续前进。不过，这些障碍物并不是坚不可摧的。左侧障碍物被撞 $a$ 次之后就会破碎，右侧被撞 $b$ 次后也会破碎。障碍物被破坏后，蚂蚁通过破碎的障碍物就会从棍子上掉下去。注意，计算障碍物被撞击次数时，两侧分别独立计数，并且最后一次撞击导致障碍物破碎的那只蚂蚁会先调头，并不会马上掉下去。 问所有蚂蚁全部从棍子上掉下去需要多少秒？

每个测试点仅包含一组数据。 第一行包含三个整数 $n$、$a$、$b$（$1 \le n \le 10^6$，$1 \le a, b \le 10^9$），分别表示蚂蚁的数量，左端障碍物被撞击 $a$ 次会破碎，右端障碍物被撞击 $b$ 次会破碎。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$, $a_i < a_{i+1}$），表示每只蚂蚁的初始位置。 第三行包含 $n$ 个整数 $d_1, d_2, \cdots, d_n$（$d_i \in \{0, 1\}$），如果 $d_i = 0$，则第 $i$ 只蚂蚁初始面向左，否则面向右。

输出一行一个整数，表示所有蚂蚁全部掉下棍子需要的秒数。

$$ \begin{array}{|c|c|c|c|} \hline \textbf{时间} & \textbf{事件} & \textbf{左端被撞次数} & \textbf{右端被撞次数} \\ \hline 2 & \text{第 1 只蚂蚁撞左障碍物} & 1 & 0 \\ \hline 999999998 & \text{第 2 只蚂蚁撞右障碍物} & 1 & 1 \\ \hline 1000000000.5 & \text{第 1 只蚂蚁和第 2 只蚂蚁在距离左端 999999998.5 处相遇} & 1 & 1 \\ \hline 1000000003 & \text{第 2 只蚂蚁撞右障碍物} & 1 & 2 \\ \hline 1999999999 & \text{第 1 只蚂蚁撞左障碍物} & 2 & 2 \\ \hline 2000000001.5 & \text{第 1 只蚂蚁和第 2 只蚂蚁在距离左端 2.5 处相遇} & 2 & 2 \\ \hline 2000000004 & \text{第 1 只蚂蚁从左端掉下} & 2 & 2 \\ \hline 3000000000 & \text{第 2 只蚂蚁撞右障碍物} & 2 & 3 \\ \hline 4000000001 & \text{第 2 只蚂蚁从左端掉下} & 2 & 3 \\ \hline \end{array} $$ 由 ChatGPT 5 翻译