Submission #950382

#	Time	Username	Problem	Language	Result	Execution time	Memory
950382		viwlesxq	Vudu (COCI15_vudu)	C++17	140 / 140	228 ms	37280 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()

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;
}

struct fenwick {
  int n;
  vector<int> t;
  fenwick(int n) {
    this -> n = n;
    t.assign(n + 1, 0);
  }
  void upd(int i, int delta) {
    for (; i <= n; i += i & -i) {
      t[i] += delta;
    }
  }
  int get(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) {
      res += t[i];
    }
    return res;
  } int cnt(int i) {
    return get(n) - get(i - 1);
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n; cin >> n;
  int a[n], idx[n + 1];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int p; cin >> p;
  vector<pair<long long, int>> v;
  long long res = 0, sum = 0;
  v.push_back({0, n});
  for (int i = 0; i < n; ++i) {
    sum += a[i];
    v.push_back({1ll * p * i + p - sum, i});
  }
  sort(all(v));
  int id = 1;
  for (int i = 0; i <= n; ++i) {
    if (i && v[i - 1].first != v[i].first) {
      id++;
    }
    idx[v[i].second] = id;
  }
  v.clear();
  fenwick fenw(id);
  sum = 0;
  fenw.upd(idx[n], 1);
  for (int i = 0; i < n; ++i) {
    sum += a[i];
    res += fenw.cnt(idx[i]);
    fenw.upd(idx[i], 1);
  }
  cout << res;
}

• Subtask 1: 140 / 140