Submission #950099

#	Time	Username	Problem	Language	Result	Execution time	Memory
950099		vjudge1	Vudu (COCI15_vudu)	C++17	112 / 140	468 ms	65536 KiB

vudu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define int long long
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

template<class S, class T>
bool chmin(S& a, const T& b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
  return a < b ? (a = b) == b : false;
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n; cin >> n;
  int a[n + 1];
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  int p; cin >> p;
  ordered_set st;
  int res = 0, sum = 0;
  st.insert(0);
  for (int i = 1; i <= n; ++i) {
    sum += a[i];
    res += size(st) - st.order_of_key(p * i - sum);
    st.insert(p * i - sum);
  }
  cout << res;
}

• Subtask 1: 112 / 140