比赛 期末考试1 评测结果 AAAAAAAAAA
题目名称 Interactive 最终得分 100
用户昵称 djyqjy 运行时间 1.437 s
代码语言 C++ 内存使用 32.22 MiB
提交时间 2026-02-08 09:43:45
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
int T;
void clear();
const int N=200010;
int n,k,q;
int a[N];
int pre[N];
int st[N][20];
int last[N];
void init()
{
    for(int i=0;i<=n;i++) st[i][0]=pre[i];
    for(int i=1;i<=18;i++)
        for(int j=0;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    return;
}
int query(int l,int r)
{
    int d=__lg(r-l+1);
    return min(st[l][d],st[r-(1<<d)+1][d]);
}
void init2()
{
    for(int i=1;i<=n;i++) st[i][0]=last[i];
    for(int i=1;i<=18;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    return;
}
int query2(int l,int r)
{
    int d=__lg(r-l+1);
    return max(st[l][d],st[r-(1<<d)+1][d]);
}
int res[N];
void work()
{
    freopen("tioj_interactive.in","r",stdin);
    freopen("tioj_interactive.out","w",stdout);
    clear();
    n=re();k=re();
    for(int i=1;i<=n;i++) a[i]=re(),pre[i]=pre[i-1]+a[i];
    init();
    for(int i=1;i<=n;i++)
    {
        // cout<<"***"<<i<<' '<<pre[i]<<' '<<query(0,i)<<endl;
        if(pre[i]-query(0,i)<k)
        {
            last[i]=0;
            continue;
        }
        int l=0,r=i,mid;
        while(l<r)
        {
            mid=(l+r+1)/2;
            if(pre[i]-query(mid,i)>=k) l=mid;
            else r=mid-1;
        }
        last[i]=l+1;
    }
    // for(int i=1;i<=n;i++) cout<<last[i]<<' ';cout<<endl;
    init2();
    // cout<<query2(5,7)<<endl;
    for(int i=1;i<=n;i++)
    {
        if(query2(1,i)<1) continue;
        int l=1,r=i,mid;
        while(l<r)
        {
            mid=(l+r+1)/2;
            if(query2(mid,i)>=mid) l=mid;
            else r=mid-1;
        }
        // cout<<"******"<<i<<' '<<l<<endl;
        res[i-l+1]++;
        res[i-1+1+1]--;
    }
    // for(int i=1;i<=n;i++) cout<<res[i]<<' ';cout<<endl;
    for(int i=1;i<=n;i++) res[i]+=res[i-1];
    for(int i=1;i<=n;i++) res[i]+=res[i-1];
    q=re();
    for(int i=1;i<=q;i++) printf("%lld\n",res[re()]);
    return;
}
signed main()
{
    T=1;
    while(T--) work();
    return 0;
}
void clear()
{
    return;
}