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