Submission #1688250

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, K, A[200000];

template<typename T> class BinaryIndexedTree {
  vector<T> vec;
  const ll n;

public:
  BinaryIndexedTree(T _n) : vec(_n + 1), n(_n) {}

  T query(ll x) {
    T ret = 0;
    for(ll i = x; i > 0; i -= i & (-i)) ret += vec[i];
    return ret;
  }

  void update(ll x, T k) { for(ll i = x; i <= n; i += i & (-i)) vec[i] += k; }
};

int main(void) {
  cin >> N >> K;
  A[0] = 0;
  REP(i, 1, N + 1) cin >> A[i];

  REP(i, 1, N + 1) A[i] += A[i - 1];
  REP(i, 0, N + 1) A[i] -= i * K;

  vector<ll> vec(N + 1);
  REP(i, 0, N + 1) vec[i] = A[i];
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  REP(i, 0, N + 1) A[i] = lower_bound(vec.begin(), vec.end(), A[i]) - vec.begin() + 1;

  BinaryIndexedTree<ll> bit(N + 1);
  ll ans = 0;
  REP(i, 0, N + 1) {
    ans += bit.query(A[i]);
    bit.update(A[i], 1);
  }
  cout << ans << endl;
}

Submission Info

Judge Result