[R78F]归零 - 代码源竞赛平台

时空限制

1S/512M

题目描述

一台计数器依次读取整数记录。读取一条记录时，先将记录中的整数加到当前读数上；如果得到的读数为负数，就立即将它归零。

给定长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$，以及一个非负整数 $k$。对于每个非空连续子数组 $a_l,a_{l+1},\ldots,a_r$，将计数器的读数 $x$ 重新设为 $0$，然后按照 $i=l,l+1,\ldots,r$ 的顺序，将 $x$ 更新为

$$x=\max(0,x+a_i).$$

求有多少个下标对 $(l,r)$ 满足 $1\le l\le r\le n$，并且读完该子数组后，计数器的读数恰好为 $k$。不同子数组的读取过程都从 $x=0$ 重新开始，互不影响。

格式

输入格式

第一行包含一个正整数 $n$ 和一个非负整数 $k$，分别为数组的长度和要求的最终读数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 为第 $i$ 条记录中的整数。

输出格式

输出一个非负整数，表示最终读数恰好为 $k$ 的非空连续子数组数量。

样例

样例输入 #1

3 2
2 -3 2

样例输出 #1

4

样例解释 #1

符合要求的区间为 $[1,1],[1,3],[2,3],[3,3]$。对于 $[1,3]$，$x$ 的变化为 $0\to2\to0\to2$。

样例输入 #2

3 0
1 -1 0

样例输出 #2

5

样例解释 #2

除区间 $[1,1]$ 外，其余五个非空区间的最终结果都为 $0$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$2000$	无
$2$		$2\times10^5$	A
$3$			B
$4$	$40$		无特殊限制

特殊性质 A：$k=0$。

特殊性质 B：对于所有 $1\le i\le n$，满足 $a_i\ge0$。

对于 $100\%$ 的数据，满足 $1\le n\le2\times10^5$，$0\le k\le10^{14}$，$-10^9\le a_i\le10^9$。输入中的所有数均为整数。