You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $N$ 只蚂蚁在数轴上，编号从 1 到 N。蚂蚁 $i (1 ≤ i ≤ N)$ 位于坐标 $X_i$，面向正方向或负方向。初始时，所有蚂蚁都在不同的坐标。每只蚂蚁的方向由长度为 N 的二进制字符串 S 表示，其中蚂蚁 i 面向如果是负方向 $S_i$ 是 0，面向如果是正方向 S_i 是 1。 设当前时间为 0，蚂蚁们以每单位时间 1 单位的速度朝各自的方向移动，直到时间 (T + 0.1)。如果多只蚂蚁到达同一坐标，它们会穿过彼此而不改变方向或速度。在 (T + 0.1) 单位时间后，所有蚂蚁停止。 找出在时间 (T + 0.1) 之前蚂蚁 i 和蚂蚁 j 会穿过彼此的蚂蚁对 (i, j) 的数量，满足 1 ≤ i < j ≤ N。

输入格式

输入从标准输入给出，格式如下： 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 655328858
01001110011101
-880548713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379348552 -237481538 -44636942 352721061 695864366

14

约束条件

$2 ≤ N ≤ 2 × 10^5$ $1 ≤ T ≤ 10^9$ S 是长度为 N 的字符串，由 0 和 1 组成。 $-10^9 ≤ X_i ≤ 10^9 (1 ≤ i ≤ N)$ $X_i ≠ X_j (1 ≤ i < j ≤ N)$ N, T, 和 $X_i (1 ≤ i ≤ N)$是整数。