幽灵蚂蚁

题目描述

数轴上有 $N$ 只蚂蚁,编号 $1$ 到 $N$。蚂蚁 $i$ $(1 \le i \le N)$ 从坐标 $X_i$ 出发,面朝正方向或负方向。最初,所有蚂蚁位于互不相同的坐标。每只蚂蚁的方向由长度为 $N$ 的二进制字符串 $S$ 表示:若 $S_i$ 为 0,则蚂蚁 $i$ 面朝负方向;若 $S_i$ 为 1,则面朝正方向。

设当前时间为 0,蚂蚁以速度 1 沿各自方向移动,持续 $(T+0.1)$ 个单位时间,直到时间 $(T+0.1)$。当多只蚂蚁到达同一坐标时,它们会穿过彼此,方向与速度均不发生改变。经过 $(T+0.1)$ 个单位时间后,所有蚂蚁停止。

求满足 $1 \le i \lt j \le N$ 且蚂蚁 $i$ 和蚂蚁 $j$ 从现在起到时间 $(T+0.1)$ 之前会相互穿过的对数 $(i, j)$。

输入格式

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

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

输出格式

输出答案。

样例

6 3
101010
-5 -1 0 1 2 4

5

以下五对蚂蚁会相互穿过:

• 蚂蚁 3 和蚂蚁 4 在时间 0.5 相互穿过。
• 蚂蚁 5 和蚂蚁 6 在时间 1 相互穿过。
• 蚂蚁 1 和蚂蚁 2 在时间 2 相互穿过。
• 蚂蚁 3 和蚂蚁 6 在时间 2 相互穿过。
• 蚂蚁 1 和蚂蚁 4 在时间 3 相互穿过。

没有其他蚂蚁对会相互穿过,因此输出 5。

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

14

数据范围

• $2 \le N \le 2 \times 10^{5}$
• $1 \le T \le 10^{9}$
• $S$ 是由 0 和 1 组成的长度为 $N$ 的字符串。
• $-10^{9} \le X_i \le 10^{9}$ $(1 \le i \le N)$
• $X_i \neq X_j$ $(1 \le i \lt j \le N)$
• $N$、$T$、$X_i$ $(1 \le i \le N)$ 均为整数。