Submission #380207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
380207	2021-03-20T13:59:15 Z	alrad	Vudu (COCI15_vudu)	C++17	140 / 140	930 ms	65536 KB

vudu

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;
using ll = long long;

/*
#pragma comment(linker, "/STACK:256000000")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

template <class T> inline T gcd(T a , T b) { return !a ? b : gcd(b % a , a); }
template <class T> inline T lcm(T a , T b) { return (a * b) / gcd(a , b) ; }

mt19937 rnd(time(0));

#define all(x) x.begin(), x.end()
#define debug(x) { cerr << #x << " = " << x << endl; }

const int N = 1e6 + 2;

long long T[N + 5];

void upd(int i, int D) {
  for (; i < N; i = (i | (i + 1))) {
    T[i] += D;
  }
  return;
}

long long calc(int R) {
  long long result = 0;
  for (; R >= 0; R = (R & (R + 1)) - 1) {
    result += T[R];
  }
  return result;
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int P;
  cin >> P;
  for (int i = 0; i < n; i++) {
    a[i] -= P;
  }
  vector<ll> pref(n, 0ll);
  for (int i = 0; i < n; i++) {
    pref[i] = a[i];
    if (i) {
      pref[i] += pref[i - 1];
    }
  }
  int pos = -1;
  auto compress = [&](void) {
    vector<long long> b = pref;
    b.push_back(0);
    sort(all(b));
    int key = 1;
    unordered_map<long long, int> ct;
    for (int i = 0; i < n + 1; i++) {
      if (ct[b[i]] == 0) {
        ct[b[i]] = key;
        key++;
      }
    }
    for (int i = 0; i < n; i++) {
      pref[i] = ct[pref[i]];
    }
    pos = ct[0];
    return;
  };
  compress();
  upd(pos, +1);
  long long ans = 0ll;
  for (int i = 0; i < n; i++) {
    ans += calc(pref[i]);
    upd(pref[i], +1);
  }
  cout << ans << '\n';
  return;
}

signed main() {
  ios_base :: sync_with_stdio(0);
  cin.tie(0) , cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	876 KB	Output is correct
2	Correct	3 ms	748 KB	Output is correct
3	Correct	3 ms	748 KB	Output is correct
4	Correct	859 ms	65536 KB	Output is correct
5	Correct	469 ms	44964 KB	Output is correct
6	Correct	758 ms	60648 KB	Output is correct
7	Correct	784 ms	62648 KB	Output is correct
8	Correct	690 ms	55380 KB	Output is correct
9	Correct	930 ms	65536 KB	Output is correct
10	Correct	752 ms	61164 KB	Output is correct