| 比赛 |
期末考试1 |
评测结果 |
AAWTTTWTWW |
| 题目名称 |
Interactive |
最终得分 |
20 |
| 用户昵称 |
zcx |
运行时间 |
4.467 s |
| 代码语言 |
C++ |
内存使用 |
4.74 MiB |
| 提交时间 |
2026-02-08 09:51:08 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
int n,k;
int a[N],pre[N],tag[N],f[N];
//int check(int l,int r){
// int fl=l;
// while(l<r){
// int mid=(l+r+1)>>1;
// if(pre[mid]-pre[fl-1]>=k) r=mid-1;
// else l=mid;
// }
// if(pre[l]-pre[fl-1]>=k) return -1;
// return l;
//}
void B_plan(){
int j=1,ans=0;
for(int i=1;i<=n;i++){
while(pre[j]-pre[i-1]<k&&j<=n)j++;
if(j==n+1) break;
ans+=n-j+1;
}
cout<<ans<<endl;
}
int main()
{
freopen("tioj_interactive.in","r",stdin);
freopen("tioj_interactive.out","w",stdout);
int flag=1;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=a[i]+pre[i-1];
if(a[i]<0) flag=0;
}
if(flag){
B_plan();
return 0;
}
for(int len=1;len<=n;len++){
f[len]=f[len-1];
for(int i=1;i<=n-len+1;i++){
if(pre[i+len-1]-pre[i-1]>=k || tag[i] || tag[i+1]) tag[i]=1,f[len]++;
else tag[i]=0;
}
}
int Q;
cin>>Q;
while(Q--){
int x;
cin>>x;
cout<<f[x]<<endl;
}
return 0;
}