比赛 |
2024暑假C班集训C |
评测结果 |
WAWAWAWWWW |
题目名称 |
灯笼 |
最终得分 |
30 |
用户昵称 |
flyfree |
运行时间 |
0.674 s |
代码语言 |
C++ |
内存使用 |
7.24 MiB |
提交时间 |
2024-07-12 10:55:17 |
显示代码纯文本
#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&&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;
}