Ghost Ants

题目描述

数轴上有 $N$ 只蚂蚁，编号为 $1$ 到 $N$。蚂蚁 $i$ $(1 \leq i \leq N)$ 从坐标 $X_i$ 出发，面向正向或负向。起始时刻所有蚂蚁的位置互不相同。每只蚂蚁面向的方向由长度为 $N$ 的二进制字符串 $S$ 表示：若 $S_i$ 为 $0$ 则蚂蚁 $i$ 朝负方向，若 $S_i$ 为 $1$ 则朝正方向。 设当前时间为 $0$，蚂蚁以速度 $1$（单位距离/单位时间）沿各自方向运动，持续 $(T+0.1)$ 的时间，直到时间 $(T+0.1)$。若多只蚂蚁到达同一坐标，它们互相通过且不改变方向与速度。经过 $(T+0.1)$ 的时间后，所有蚂蚁停止。 求满足 $1 \leq i < j \leq N$ 且蚂蚁 $i$ 与蚂蚁 $j$ 在此时间范围内相遇（互相经过）的对数 $(i, j)$ 的数量。

输入格式

输入从标准输入按以下格式给出： $N$ $T$ $S$ $X_1$ $X_2$ ... $X_N$

输出格式

输出答案。

6 3
101010
-5 -1 0 1 2 4

5

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

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 &lt; j \leq N) $N$, $T$ 和 $X_i$ $(1 \leq i \leq N)$ 均为整数。下面五对蚂蚁会互相经过：

蚂蚁 $3$ 和蚂蚁 $4$ 在时间 $0.5$ 相遇。 蚂蚁 $5$ 和蚂蚁 $6$ 在时间 $1$ 相遇。 蚂蚁 $1$ 和蚂蚁 $2$ 在时间 $2$ 相遇。 蚂蚁 $3$ 和蚂蚁 $6$ 在时间 $2$ 相遇。 蚂蚁 $1$ 和蚂蚁 $4$ 在时间 $3$ 相遇。

没有其他对会相遇，因此输出 $5$。

标签: AtCoder|abc360D

来源

AtCoder|abc360D