比赛 期末考试1 评测结果 WWTWWTTWTT
题目名称 Interactive 最终得分 0
用户昵称 ychyyx 运行时间 6.456 s
代码语言 C++ 内存使用 33.78 MiB
提交时间 2026-02-08 12:13:12
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,q;
int a[200005];
long long k;
long long f[200005][25];
int x;
long long stl(int l,int r){
    int k=-1;
    while(l+(1<<(k+1))-1<=r)    k++;
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
bool check(){
    for(int i=1;i<=n;i++){
        if(a[i]<0)  return false;
    }
    return true;
}
int main(){
    freopen("tioj_interactive.in","r",stdin);
    freopen("tioj_interactive.out","w",stdout);
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i][0]=f[i-1][0]+a[i];
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    if(k<=0){
        long long ans=(long long)(n*(n+1)/2);
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            scanf("%d",&x);
            printf("%lld\n",ans);
        }
    }else if(check()){
        
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            scanf("%d",&x);
            int ans=0;
            for(int j=1;j<=n;j++){
                for(int l=max(0,j-x);l<=j;l++){
                    if(f[j][0]-f[l][0]>=k)
                        ans++;
                }
            }
            printf("%d\n",ans);
        }
    }else if(k==1){
        for(int i=1;i<=n;i++){
            if(a[i]>0)  f[i][0]=1;
        }
        for(int j=1;j<=20;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                f[i][j]=f[i][j-1]+f[i+(1<<(j-1))][j-1];
            }
        }
        scanf("%d",&q); 
        for(int i=1;i<=q;i++){
            scanf("%d",&x);
        }
    }else{
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            scanf("%d",&x);
            int ans=0;
            for(int j=1;j<=n;j++){
                for(int l=max(0,j-x);l<=j;l++){
                    if(f[j][0]-f[l][0]>=k){ 
                        ans++;
                        if(l>j-x){
                            ans++;
                        }
                    } 
                }
            }
            printf("%d\n",ans);
        }   
    }
    return 0;
}