Submission #2214897

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF=1e18;

typedef pair<ll,ll> P;

int N,K;
ll ans;
ll a[200005],s[200005];
P b[200005];

int bit[(1<<18)+1];

ll sum(int i){
  ll ret=0;
  while(i){
    ret+=bit[i];
    i-=(i&-i);
  }
  return ret;
}

void add(int i,int x){
  while(i<(1<<18)){
    bit[i]+=x;
    i+=(i&-i);
  }
}

int main() {

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>K;

for(int i=1; i<=N; i++){
  cin>>a[i]; 
  a[i]-=K;
}

for(int i=1; i<=N; i++){
  s[i]=a[i]+s[i-1];
  if(s[i]>=0) ans++;
}

for(int i=1; i<=N; i++){
  b[i].first=s[i];
  b[i].second=i;
}

sort(b+1,b+N+1);

int j=0; ll x=-INF;

for(int i=1; i<=N; i++){
  if(b[i].first>x){
    j++; 
    x=b[i].first;
  }
    b[i].first=j;
}

for(int i=1; i<=N; i++){
  s[b[i].second]=b[i].first;
}

for(int i=1; i<=N; i++){
  ans+=sum(s[i]);
  add(s[i],1);
}

cout<<ans<<endl;

}

Submission Info

Judge Result