分数: 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