题目详情

U49476.玩具士兵

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

Yuilice有NN只玩具士兵在数轴上，其中第ii只玩具士兵的下标XiX_i，每只玩具士兵每秒向固定方向走一格，SiS_i表示第i只玩具士兵的行走方向：

  • Si=0S_i = 0 : 表示下标为XiX_i的玩具士兵面朝数轴负方向
  • Si=1S_i = 1 : 表示下标为XiX_i的玩具士兵面朝数轴正方向

若两玩具士兵相遇,并且他们既不改变速度也不改变方向的情况下，请问在TT秒以内，有多少玩具士兵相遇

数据约束

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤T≤1091 \leq T \leq 10^9
  • SS 由 0≤Si≤10 \leq S_i \leq 1 组成，长度为NN的字符串
  • −109≤Xi≤109(1≤i≤N)-10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • Xi≠Xj(1≤i<j≤N)X_i \neq X_j (1 \leq i < j \leq N)
  • N,T,Xi(1≤i≤N)N, T, X_i (1 \leq i \leq N) 为整数

输入格式

输入内容由标准输入法提供，格式如下

NN TT
SS
X1X_1 X2X_2 ... XNX_N

输出格式

输出一个整数代表答案

输入输出样例

  • 输入#1

    6 3
101010
-5 -1 0 1 2 4

    输出#1

    5

  • 输入#2

    13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

    输出#2

    14

说明/提示

样例1解释：

以下五对玩具士兵相遇的时间：

  • 玩具士兵3和玩具士兵4在0.5时相遇。
  • 玩具士兵5和玩具士兵6在1时相遇。
  • 玩具士兵1和玩具士兵2在2时相遇。
  • 玩具士兵3和玩具士兵6在2时相遇。
  • 玩具士兵1和玩具士兵4在3时相遇。
首页