记录编号	590916	评测结果	AAAAAAAAAA
题目名称	灯笼	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	0.707 s
提交时间	2024-07-12 18:17:28	内存使用	7.26 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
ll  n,m,x,p,cnt,rz,ans,o[MAXN];
ll nxt[MAXN],used0[MAXN],used1[MAXN],cf[MAXN];
ll dis[MAXN],len,_len;//离散化 
ll s[MAXN],sz[MAXN];//前缀和
ll tr[MAXN]; 
bool cmp(ll a,ll b){
    return a>b;
}
ll ef(ll res){
    ll l=1,r=len;
    while(l<r){
        ll mid=(r+l)/2;
        if(res>dis[mid])l=mid+1;
        else r=mid; 
    }
    return l;
}
ll lowbit(ll idx){
    return idx&(-idx);
}
void add_(ll idx,ll res){
    while(idx<=len){
        tr[idx]+=res;
        idx+=lowbit(idx);
    }
}
ll re(ll idx){
    ll res=0;
    while(idx>0){
        res+=tr[idx];
        idx-=lowbit(idx);
    }
    return res;
}
int main(){
    freopen("lantern.in","r",stdin);
    freopen("lantern.out","w",stdout);
    cin>>n>>m>>x;
    for(ll i=1;i<=n;i++){
        cin>>p;
        if(p<0){
            if(!used0[-p]){
                used0[-p]=i;
                cf[i]++;
            }else{
                nxt[used0[-p]]=i;
                used0[-p]=i;
            }
        }else{
            if(!used1[p]){
                used1[p]=i;
                cf[i]++;
            }else{
                nxt[used1[p]]=i;
                used1[p]=i;
            }
        }
        nxt[i]=n+1;
        s[i]=s[i-1]+p;
        sz[i]=s[i];
        o[i]=p;
        dis[++len]=s[i]-x;
    }
    sort(dis+1,dis+1+len,cmp);
    for(ll i=1;i<=n;i++){
        if(dis[i]==dis[i+1]){
            dis[i]=-1e9;
            _len++;
        }
    }
    sort(dis+1,dis+1+len,cmp);
    len-=_len;
    sort(dis+1,dis+1+len);
    dis[++len]=LONG_LONG_MAX;
//    for(ll i=1;i<=len;i++)cout<<dis[i]<<endl;
//    cout<<ef(6)<<endl;
//    for(ll i=1;i<=n;i++){
//        cout<<s[i]<<" ";
//    }
//    cout<<endl;
    for(ll i=1;i<=n;i++){
        s[i]=ef(s[i]-x);
//        cout<<s[i]<<" ";
    }
//    cout<<endl;
    for(ll i=1;i<=n;i++){   
        while((cnt<m||(cf[rz+1]==0&&cnt==m))&&rz<n){
            rz++;
            cnt+=cf[rz];
//            cout<<rz<<" "<<cnt<<" "<<cf[rz]<<endl;
            add_(s[rz],1);
        }
//        cout<<i<<" "<<rz<<" "<<cnt<<endl;
//        cout<<ef(sz[i-1])<<endl;
        add_(s[i],-1);
        ans+=re(len)-re(ef(sz[i-1])-1);
        if(nxt[i]>rz){
            cf[nxt[i]]=1;
            cnt--;
        }
    }
    ans*=2;
    if(m>=1)for(ll i=1;i<=n;i++){
        if(o[i]>=x)ans++;
    }
    cout<<ans<<endl;
    return 0;
}