103603: [Atcoder]ABC360 D - Ghost Ants

Problem Statement

There are $N$ ants on a number line, labeled $1$ to $N$. Ant $i$ $(1 \leq i \leq N)$ starts at coordinate $X_i$ and faces either a positive or negative direction. Initially, all ants are at distinct coordinates. The direction each ant is facing is represented by a binary string $S$ of length $N$, where ant $i$ is facing the negative direction if $S_i$ is 0 and the positive direction if $S_i$ is 1.

Let the current time be $0$, and the ants move in their respective directions at a speed of $1$ unit per unit time for $(T+0.1)$ units of time until time $(T+0.1)$. If multiple ants reach the same coordinate, they pass through each other without changing direction or speed. After $(T+0.1)$ units of time, all ants stop.

Find the number of pairs $(i, j)$ such that $1 \leq i < j \leq N$ and ants $i$ and $j$ pass each other from now before time $(T+0.1)$.

Constraints

• $2 \leq N \leq 2 \times 10^{5}$
• $1 \leq T \leq 10^{9}$
• $S$ is a string of length $N$ consisting of 0 and 1.
• $-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$, and $X_i$ $(1 \leq i \leq N)$ are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

6 3
101010
-5 -1 0 1 2 4

Sample Output 1

5

The following five pairs of ants pass each other:

• Ant $3$ and ant $4$ pass each other at time $0.5$.
• Ant $5$ and ant $6$ pass each other at time $1$.
• Ant $1$ and ant $2$ pass each other at time $2$.
• Ant $3$ and ant $6$ pass each other at time $2$.
• Ant $1$ and ant $4$ pass each other at time $3$.

No other pairs of ants pass each other, so print $5$.

Sample Input 2

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

Sample Output 2

14

问题陈述

在数轴上有N只蚂蚁，标记为1到N。蚂蚁i（1≤i≤N）从坐标X_i开始，面向正方向或负方向。最初，所有蚂蚁都在不同的坐标上。每只蚂蚁的朝向由长度为N的二进制字符串S表示，其中如果S_i是0，蚂蚁i面向负方向；如果S_i是1，蚂蚁i面向正方向。

当前时间为0，蚂蚁们以每单位时间1个单位的速度向各自的方向移动T+0.1个单位时间，直到时间T+0.1。如果有多个蚂蚁到达同一个坐标，它们会相互穿过，不改变方向或速度。在T+0.1个单位时间后，所有蚂蚁停止。

找出有多少对(i, j)满足1≤i< j≤N，蚂蚁i和j在时间(T+0.1)之前相互穿过。

约束条件

• 2≤N≤2×10^5
• 1≤T≤10^9
• S是由0和1组成的长度为N的字符串。
• -10^9≤X_i≤10^9（1≤i≤N）
• X_i≠X_j（1≤i
• N、T和X_i（1≤i≤N）是整数。

输入

输入从标准输入以以下格式给出：

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

输出

打印答案。

样本输入1

6 3
101010
-5 -1 0 1 2 4

样本输出1

5

以下五对蚂蚁相互穿过：

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

没有其他蚂蚁对相互穿过，所以打印5。

样本输入2

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

样本输出2

14