P2629 好消息，坏消息

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=2e6+10;
int n;
int q[N];
int a[N];
long long s[N];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(int i=1;i<2*n;i++){s[i]=s[i-1]+a[i];}int ans=0;int tt=-1,hh=0;for(int i=1;i<2*n;i++){if(tt>=hh&&q[hh]<i-n+1) hh++;while(tt>=hh&&s[q[tt]]>=s[i]) tt--;q[++tt]=i;if(i>=n){if(s[q[hh]]>=s[i-n]) ans++;}}cout<<ans<<endl;return 0;
}