*L9魔力药剂2
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
汤姆想要制作一种魔力药剂，为此他购买了一批材料，每种材料包含的魔力值可能不同。汤姆将这些材料从左到右排成一排，编号分别为1、2、...、n。接下来他想要从中选出一段连续区间[L,R] （1<=L<=R<=n）,并将区间内的材料全部用于制作药剂（即编号为L、L+1、...、R的材料）。 在制作过程中，按编号次序依次加入材料，每当汤姆加入一种材料（假设该材料包含的魔力值为k），药剂的魔力值也会增加k。但是当药剂的魔力值超过最大限度M后，其魔力值就会更新为0。之后再加入新的材料，药剂的魔力值会重新从0开始累加。 请计算，有多少个区间[L,R]满足：将区间内的材料全部用于制作药剂后，药剂的魔力值不为0。
例如：n=4，这4中材料的魔力值分别为1、2、1、3；M=3，表示魔力药剂的魔力值最大限度为3。有以下区间满足要求： [1,1]、[1,2]、[1,4]、[2,2]、[2,3]、[3,3]、[4,4]，共7个。
Format
Input
第一行包含一个整数n，表示材料的数量。 第二行包含n个整数k1,k2,...kn，表示每种材料包含的魔力值，整数之间以一个空格隔开。 第三行包含一个整数M，表示魔力药剂的魔力值最大限度。
Output
一个整数，表示满足题目要求的区间数量。
Samples
4
1 2 1 3
3
7
Limitation
测试点1~10：1<=n<=2*105,1<=ki<=109,1<=M<=109.
2025春学期信奥第7-9次课0404.12.19
- 状态
- 已结束
- 规则
- IOI
- 题目
- 37
- 开始于
- 2025-4-4 9:15
- 结束于
- 2025-4-25 5:15
- 持续时间
- 500 小时
- 主持人
-
admin
- 参赛人数
- 26