题目详情题解（0）讨论（0）提交记录（0）

CF1994C.Hungry Games

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

题目大意

Yaroslav 正在玩一款电脑游戏，他的角色遇到了 nn 个蘑菇，第 ii 个蘑菇的毒性定义为 aia_i。Yaroslav 可以选择两个整数 1≤l≤r≤n1\le l\le r\le n，并操控他的角色依次食用第 l,l+1,…,rl,l+1,\dots,r 个蘑菇。

Yaroslav 的角色有一个中毒属性 gg，初始为 00。当他食用第 ii 个蘑菇时，gg 会增加 aia_i，若此时 gg 超过了一个预设的最大中毒值 xx，则 gg 会重置为 00。

Yaroslav 想知道有多少种选择 l,rl,r 的方案能使他的角色食用完蘑菇后，中毒属性 gg 不为 00。

输入格式

输入数据的第一行包括一个整数 t(1≤t≤104)t\left(1\le t\le10^4\right)，表示测试用例的组数。

对于每个测试用例：

  • 第一行包括两个整数n,xn,x (1≤n≤2×105,1≤x≤109)\left(1\le n\le2\times10^5,1\le x\le10^9\right)。
  • 第二行包括 nn 个整数，依次表示 a1,a2,…,ana_1,a_2,\dots,a_n (1≤ai≤109)\left(1\le a_i \le10^9\right)。

保证 ∑n≤2×105\sum n \le 2\times 10^5

输出格式

对于每个测试用例，输出一个整数，即符合题目条件的方案数。

输入输出样例

  • 输入#1

    5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000

    输出#1

    8
2
0
10
7

说明/提示

null

输入解题思路，AI测评打分。不知道怎么写?

首页