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