답안 #380207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380207 2021-03-20T13:59:15 Z alrad Vudu (COCI15_vudu) C++17
140 / 140
930 ms 65536 KB
#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;
}
# 결과 실행 시간 메모리 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