Submission #648979

#	Time	Username	Problem	Language	Result	Execution time	Memory
648979		tvladm2009	Vudu (COCI15_vudu)	C++14	140 / 140	225 ms	47232 KiB

vudu

#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 / 140