比赛 |
2024暑假C班集训C |
评测结果 |
WAWTTWTTTT |
题目名称 |
灯笼 |
最终得分 |
10 |
用户昵称 |
123 |
运行时间 |
12.065 s |
代码语言 |
C++ |
内存使用 |
5.28 MiB |
提交时间 |
2024-07-12 10:38:31 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N=100010;
int n,m,x,a[N],mi=1e9;
long long cnt[N],b[N],ret=0;
int check(int i,int j)
{
if (i!=j && b[max(i,j)]-b[min(i,j)]+1<=m && cnt[max(i,j)]-cnt[min(i,j)-1]>=x) return 1;
return 0;
}
int main() {
freopen("lantern.in","r",stdin);
freopen("lantern.out","w",stdout);
scanf("%d%d%d",&n,&m,&x);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]<mi)
{
mi=a[i];
}
cnt[i]=a[i];
if (!mp[a[i]])
{
mp[a[i]]=1;
b[i]++;
}
if (a[i]>=x)
{
ret++;
}
}
for (int i=1;i<=n;i++)
{
cnt[i]+=cnt[i-1];
b[i]+=b[i-1];
}
if (mi>=0)
{
for (int i=1;i<=n;i++)
{
int l=i+1,r=n,q=0;
while (l<=r)
{
int mid=(l+r)/2;
if (check(i,mid))
{
l=mid+1;
q=mid;
}
else
{
r=mid-1;
}
}
ret+=(q-i+1)*2;
}
}
else
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (check(i,j))
{
ret++;
}
}
}
}
printf("%lld",ret);
}