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