oj.uz

Submission #648979

# Submission time Handle Problem Language Result Execution time Memory
648979 2022-10-08T21:33:54 Z tvladm2009 Vudu (COCI15_vudu) C++14
140 / 140
 225 ms 47232 KB 
#include <bits/stdc++.h>
#define int ll

using ll = long long;

int const nmax = 1000000;

int v[5 + nmax], sp[5 + nmax];
int ind[5 + nmax], aib[5 + nmax];
std::pair<int, int> aux[1 + nmax];

void normalize(int n) {
  for(int i = 1;i <= n; i++)
    aux[i] = {sp[i], i};
  std::sort(aux + 1, aux + n + 1);
  int cnt = 1;
  ind[aux[1].second] = 1;
  for(int i = 1;i <= n; i++) {
    if(aux[i].first != aux[i - 1].first)
      cnt++;
    ind[aux[i].second] = cnt;
  }
}

void update(int x) {
  for(int i = x;i <= nmax; i += i & -i)
    aib[i]++;
}

int query(int x) {
  int ans = 0;
  for(int i = x;1 <= i; i -= i & -i)
    ans += aib[i];
  return ans;
}

signed main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  long long n, p;
  std::cin >> n;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  std::cin >> p;
  for(int i = 1;i <= n; i++) {
    v[i] -= p;
    sp[i] = sp[i - 1] + v[i];
  }

  normalize(n);
  ll ans = 0;
  for(int i = 1;i <= n; i++) {
    ans += query(ind[i]);
    update(ind[i]);
  }
  for(int i = 1;i <= n; i++) {
    if(sp[i] >= 0)
      ans++;
  }
  std::cout << ans;
  return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 225 ms 45664 KB Output is correct
5 Correct 138 ms 26040 KB Output is correct
6 Correct 184 ms 40528 KB Output is correct
7 Correct 194 ms 42272 KB Output is correct
8 Correct 208 ms 36580 KB Output is correct
9 Correct 213 ms 47232 KB Output is correct
10 Correct 189 ms 41068 KB Output is correct