比赛 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);
}