G - Ghost Ants 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

数直線上に 1 から N の番号がつけられた N 匹の蟻がいます。 蟻 i (1 \leq i \leq N) ははじめ座標 X_i にいて、正負どちらかの方向を向いています。はじめに全ての蟻は相異なる座標にいます。各蟻が向いている方向は長さ N の 01 文字列 S で表され、S_i が 0 のとき蟻 i は負の方向を向いており、 1 のとき蟻 i は正の方向を向いています。

現在を時刻 0 とし、時刻 (T+0.1) までの (T+0.1) 単位時間にわたって、N 匹の蟻がそれぞれの向いている方向に向かって単位時間あたり 1 の速さで移動します。 複数の蟻が同じ座標に到達すると、それらの蟻はすれ違い、方向や速度を変えずに通り過ぎます。 (T+0.1) 単位時間が経過したとき、すべての蟻は停止します。

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}
  • 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 < 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

以下の 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

Output

Print the answer.

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