Memo

Twitterに書くには長すぎることを書きます。Opinions are my own.

AtCoder Regular Contest 075 E - Meaningful Mean

問題: https://atcoder.jp/contests/arc075/tasks/arc075_c

公式解説は座標圧縮 + Binary Indexed Tree(BIT)だけど、Randomized Binary Search Tree(RBST)で殴ると座標圧縮しなくていいので実装が楽。(ただし定数倍遅い気がする)

signed main() {
  ll n, k; cin >> n >> k;
  vector<ll> s(n+1);
  rep(i, n) {
    ll a; cin >> a;
    s[i+1] = s[i] + a-k;
  }
  RBST<ll> st;
  ll ans = 0;
  for(int i=n-1; i>=0; i--) {
    st.insert(s[i+1]);
    int pos = st.lowerBound(s[i]);
    ans += n-i-pos;
  }
  cout << ans << endl;
}