比赛 期末考试1 评测结果 AAAAAAAAAA
题目名称 Interactive 最终得分 100
用户昵称 梦那边的美好ME 运行时间 1.339 s
代码语言 C++ 内存使用 30.81 MiB
提交时间 2026-02-08 12:03:30
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long


struct node{
    ll lm,rm,ans,sum;
    node():lm(0),rm(0),ans(0),sum(0){};
    node(ll a,ll b,ll c,ll d):lm(a),rm(b),ans(c),sum(d) {};
 
}t[810000];
 
ll n,k;
ll a[210000];
ll ans[210000];

node pushdown(node n1,node n2){
    ll a,b,c,d;
    a=max(n1.lm,n1.sum+n2.lm);
    b=max(n2.rm,n2.sum+n1.rm);
    c=max({n1.ans,n2.ans,n1.rm+n2.lm});
    d=n1.sum+n2.sum;
    return node(a,b,c,d);
}
 
 
void build(ll l,ll r,ll o){
    if(l==r){
        t[o]=node(max(a[l],0ll),max(a[l],0ll),max(a[l],0ll),a[l]);
        return;
    }
    ll mid=(l+r) / 2;
    build(l,mid,o*2);
    build(mid+1,r,o*2+1);
    t[o]=pushdown(t[o*2],t[o*2+1]);
    return;
}
 
node query(ll l,ll r,ll al,ll ar,ll o){
    if(l<=al && ar<=r)
        return t[o];
    ll mid=(al+ar)/2;
    if(r<=mid)
        return query(l,r,al,mid,o*2);
    if(l>=mid+1)
        return query(l,r,mid+1,ar,o*2+1);
    return pushdown(query(l,mid,al,mid,o*2),query(mid+1,r,mid+1,ar,o*2+1));
}


 
int main(){
    freopen("tioj_interactive.in","r",stdin);
    freopen("tioj_interactive.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for (int i=0;i<n;i++){
        cin>>a[i];
    }
    build(0,n-1,1);
    for (ll l=0,r=0;l<n;l++){
        if(r<l) r++;
        while(r<n&&query(l,r,0,n-1,1).ans<k) r++;
        if(r==n) continue;
        ans[r-l+1]++;
        ans[n-l+1]--;
    }
    for (int i=1;i<=n;i++){
        ans[i]+=ans[i-1];
    }
    for (int i=1;i<=n;i++){
        ans[i]+=ans[i-1];
    }
    ll Q;
    cin>>Q;
    while (Q--){
        ll x;
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}