Submission #2208750

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=10000;
const ll INF=1000000000;
const int MAX=100001;
const double EPS=1e-10;
using namespace std;
struct BIT{
    int bit[200010];
    int n;
    int sum(int i){
        int s=0;
        while(i>0){
            s+=bit[i];
            i-=i&-i;
        }
        return s;
    }
    void add(int i,int x){
        while(i<=n){
            bit[i]+=x;
            i+=i&-i;
        }
    }
};
ll b[200010];
map<ll,int> m;
void compress(int n){
    vector<int> v;
    for(int i=0;i<=n;i++){
        v.push_back(b[i]);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<(int)v.size();i++){
        m[v[i]]=i+1;
    }
}
int main() {
    int n;ll k;ll a[200010];
    cin>>n>>k;
    ll sum=0;
    b[0]=0;
    m[0]=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        b[i+1]=sum-(i+1)*k;
    }
    compress(n);
    BIT bit;
    bit.n=n+1;
    int ans=0;
    for(int i=0;i<=n;i++){
        int x=m[b[i]];
        cout<<x<<endl;
        ans+=bit.sum(x);
        bit.add(x,1);
    }
    cout<<ans<<endl;
    
}

Submission Info

Judge Result