Submission #950382

# Submission time Handle Problem Language Result Execution time Memory
950382 2024-03-20T09:04:35 Z viwlesxq Vudu (COCI15_vudu) C++17
140 / 140
228 ms 37280 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 228 ms 35268 KB Output is correct
5 Correct 118 ms 26560 KB Output is correct
6 Correct 175 ms 32592 KB Output is correct
7 Correct 199 ms 33048 KB Output is correct
8 Correct 166 ms 30656 KB Output is correct
9 Correct 226 ms 37280 KB Output is correct
10 Correct 195 ms 32844 KB Output is correct