Contest Duration: - (local time) (100 minutes) Back to Home
D - Ghost Ants /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 \leq i < j \leq N を満たし、今から時刻 (T+0.1) までに蟻 i と蟻 j がすれ違う整数の組 (i,j) の個数を求めてください。

### 制約

• 2 \leq N \leq 2 \times 10^{5}
• 1 \leq T \leq 10^{9}
• S01 からなる長さ N の文字列
• -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


Score : 350 points

### 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


### 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