比赛 期末考试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;
}