AT_abc360_d [ABC360D] Ghost Ants

题目描述

在数轴上有 $N$ 只蚂蚁，编号为 $1$ 到 $N$。第 $i$ 只蚂蚁（$1 \leq i \leq N$）初始时位于坐标 $X_i$，并朝着正方向或负方向。所有蚂蚁的初始坐标互不相同。每只蚂蚁朝向由一个长度为 $N$ 的 $01$ 字符串 $S$ 表示，若 $S_i$ 为 0，则第 $i$ 只蚂蚁朝负方向，若 $S_i$ 为 1，则朝正方向。

现在为时刻 $0$，在接下来的 $(T+0.1)$ 单位时间内，$N$ 只蚂蚁以每单位时间 $1$ 的速度，分别朝各自的方向移动。当多只蚂蚁到达同一坐标时，它们会直接错身而过，不改变方向和速度。$(T+0.1)$ 单位时间后，所有蚂蚁停止。

请计算满足 $1 \leq i < j \leq N$，在现在到时刻 $(T+0.1)$ 之间，第 $i$ 只蚂蚁和第 $j$ 只蚂蚁会相遇的整数对 $(i, j)$ 的数量。

输入格式

输入按以下格式从标准输入给出。

$N$ $T$ $S$ $X_1$ $X_2$ ... $X_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6 3
101010
-5 -1 0 1 2 4

输出 #1

5

输入输出样例 #2

输入 #2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

输出 #2

14

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^{5}$
• $1 \leq T \leq 10^{9}$
• $S$ 是由 0 和 1 组成的长度为 $N$ 的字符串
• $-10^{9} \leq X_i \leq 10^{9}$（$1 \leq i \leq N$）
• $X_i \neq X_j$（$1 \leq i < j \leq N$）
• $N,T,X_i$（$1 \leq i \leq N$）均为整数

样例解释 1

以下 $5$ 对蚂蚁会相遇：

• 蚂蚁 $3$ 和蚂蚁 $4$ 在时刻 $0.5$ 相遇。
• 蚂蚁 $5$ 和蚂蚁 $6$ 在时刻 $1$ 相遇。
• 蚂蚁 $1$ 和蚂蚁 $2$ 在时刻 $2$ 相遇。
• 蚂蚁 $3$ 和蚂蚁 $6$ 在时刻 $2$ 相遇。
• 蚂蚁 $1$ 和蚂蚁 $4$ 在时刻 $3$ 相遇。 除此之外，没有其他蚂蚁组合会相遇，因此输出 $5$。

由 ChatGPT 4.1 翻译