比赛 |
2024暑假C班集训C |
评测结果 |
AAAAATTTTT |
题目名称 |
灯笼 |
最终得分 |
50 |
用户昵称 |
djyqjy |
运行时间 |
10.105 s |
代码语言 |
C++ |
内存使用 |
4.54 MiB |
提交时间 |
2024-07-12 10:39:52 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=100010,L=21000,ADD=10010,LL=210000;
int n,m,x;
int like[N];
int tl[L];
long long ans;
long long suml[N];
long long ys[LL];
int jsql;
long long c[LL];
bool ldl=1;
int chaxun(long long val)
{
int l=1,r=jsql;
while(l<r)
{
int mid=(l+r)/2;
if(ys[mid]>=val) r=mid;
else l=mid+1;
}
return l;
}
void add(int w)
{
while(w<=LL)
{
c[w]++;
w+=w&-w;
}
return;
}
long long q(int w)
{
long long anssss=0;
while(w)
{
anssss+=c[w];
w-=w&-w;
}
return anssss;
}
int main()
{
freopen("lantern.in","r",stdin);
freopen("lantern.out","w",stdout);
scanf("%d%d%d",&n,&m,&x);
long long xxx=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&like[i]);
if(like[i]<0) ldl=0,xxx+=like[i];
suml[i]=suml[i-1]+like[i];
}
if(m==n)
{
ys[++jsql]=0;
for(int i=1;i<=n;i++)
{
ys[++jsql]=suml[i];
ys[++jsql]=suml[i]-x;
}
sort(ys+1,ys+1+jsql);
int xx=unique(ys+1,ys+1+jsql)-(ys+1);
add(chaxun(0));
for(int i=1;i<=n;i++)
{
ans+=q(chaxun(suml[i]-x))*2;
if(like[i]>=x) ans--;
add(chaxun(suml[i]));
}
printf("%lld",ans);
return 0;
}
else if(x<=xxx)
{
int r=0;
int jsq=0;
for(int l=1;l<=n;l++)
{
if(l!=1)
{
tl[like[l-1]+ADD]--;
if(tl[like[l-1]+ADD]==0) jsq--;
}
while(r<=n)
{
if(tl[like[r+1]+ADD]==0&&jsq+1>m) break;
r++;
if(tl[like[r]+ADD]==0) jsq++;
tl[like[r]+ADD]++;
}
if(r>n) r--;
ans+=(r-l+1)*2-1;
}
printf("%lld",ans);
return 0;
}
else if(n<=5000)
{
for(int i=1;i<=n;i++)
{
long long ll=like[i];
memset(tl,0,sizeof(tl));
tl[like[i]+ADD]++;
int jsq=1;
if(ll>=x&&jsq<=m) ans++;
for(int j=i+1;j<=n;j++)
{
ll+=like[j];
if(tl[like[j]+ADD]==0) jsq++;
tl[like[j]+ADD]++;
if(jsq>m) break;
if(ll>=x) ans+=2;
}
}
printf("%lld",ans);
return 0;
}
else
{
int r=0;
int jsq=0;
for(int l=1;l<=n;l++)
{
if(l!=1)
{
tl[like[l-1]+ADD]--;
if(tl[like[l-1]+ADD]==0) jsq--;
int ll=l,rr=r;
while(ll<rr)
{
int mid=(ll+rr+1)/2;
if(suml[l-1]+x<suml[mid]) r=mid-1;
else l=mid;
}
ans-=(ll-l)*2;
if(ll!=l) ans++;
}
r=l;
while(r<=n)
{
if(tl[like[r+1]+ADD]==0&&jsq+1>m) break;
r++;
if(suml[r]-suml[l-1]<x) ans-=(l==r?1:2);
if(tl[like[r]+ADD]==0) jsq++;
tl[like[r]+ADD]++;
}
if(r>n) r--;
ans+=(l-r+1)*2-1;
}
printf("%lld",ans);
return 0;
}
}