求助ABC Ex
  • 板块学术版
  • 楼主zimerYN-Erinnert
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/12/17 22:07
  • 上次更新2023/10/24 07:22:48
查看原帖
求助ABC Ex
271831
zimerYN-Erinnert楼主2022/12/17 22:07
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
ll a[N],b[N],st[30][N],s,sum[N],anssum=0,l[N];
inline ll query(int zuo,int you)
{
	int d=l[you-zuo+1];
	return min(st[d][zuo],st[d][you-(1<<d)+1]);
}
int main()
{
	cin>>n>>s;
	sum[0]=0;
	l[0]=-1;
	for(int i=1;i<=n;++i)l[i]=l[i/2]+1;
	for(int i=1;i<=n;++i)cin>>a[i],st[0][i]=a[i];
	for(int i=1;(1<<i)<=n;++i)
		for(int j=1;j+(1<<i)-1<=n;++j)
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	for(int i=1;i<=n;++i)cin>>b[i],sum[i]=b[i]+sum[i-1];
	for(int i=1;i<=n;++i)
	{
		int zuo=i,you=n,ans=0;
		while(zuo<=you)
		{
			int mid=zuo+you>>1;
			if(query(i,mid)<=s-(sum[mid]-sum[i-1]))ans=mid,zuo=mid+1;
			else you=mid-1;
		}
		if(ans)anssum+=ans-i+1;
	}
	cout<<anssum;
	return 0;
}
2022/12/17 22:07
加载中...