← 返回题目列表

AtCoder · abc360_d

G. 幽灵蚂蚁

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

有 N 数轴上的蚂蚁,已标记 1 to N。蚂蚁 i (1 \leq i \leq N) 从坐标开始 X_i 并且面向正方向或负方向。最初,所有蚂蚁都处于不同的坐标。每只蚂蚁所面对的方向由二进制字符串表示 S 长度 N,其中蚂蚁 i 面向负方向,如果 S_i is 0 和正方向如果 S_i is 1.

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

查找对的数量 (i, j) 这样 1 \leq i < j \leq N 和蚂蚁 i 和 j 从现在到时间之前互相传递 (T+0.1).

约束

  • 2 \leq N \leq 2 \times 10^{5}
  • 1 \leq T \leq 10^{9}
  • S 是一个长度为 N 组成 0 和 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,和 X_i (1 \leq i \leq 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