哈尔滨工业大学（威海）第九届ACM程序设计竞赛-G-Virtual Youtuber

地址：https://ac.nowcoder.com/acm/contest/624/G

思路：求前缀和，在从头开始遍历左下标l,二分查找最大<p的下标r，ans+=r-l+1

Code:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const int MAX_N=1e5+5;
int n,T;
LL p;
LL a[MAX_N];

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	for(int t=1;t<=T;++t)
	{
		cin>>n>>p;
		for(int i=1;i<=n;++i)
		{
			cin>>a[i];
			a[i]+=a[i-1];
		}
		LL ans=0;
		int k;
		for(int i=1;i<=n;++i)
		{
			k=lower_bound(a+i,a+n+1,a[i-1]+p)-a;
			if(k==n+1||a[k]>=a[i-1]+p)	--k;
			ans+=k-i+1;
		}
		cout<<"Case #"<<t<<": "<<ans<<endl;
	}
	
	return 0;
}