oj.uz

답안 #950160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950160 2024-03-20T06:03:35 Z vjudge1 Vudu (COCI15_vudu) C++17
140 / 140
 247 ms 37292 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;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 247 ms 36352 KB Output is correct
5 Correct 113 ms 22240 KB Output is correct
6 Correct 199 ms 28076 KB Output is correct
7 Correct 181 ms 31652 KB Output is correct
8 Correct 167 ms 23480 KB Output is correct
9 Correct 223 ms 37292 KB Output is correct
10 Correct 195 ms 29728 KB Output is correct