Submission #895376

#	Time	Username	Problem	Language	Result	Execution time	Memory
895376		MilosMilutinovic	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	85 ms	9332 KiB

growing

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long ans = 1e18;
  vector<int> fenw(n + 1);
  auto Modify = [&](int p, int v) {
    for (p++; p <= n; p += p & -p) {
      fenw[p] += v;
    }
  };
  auto Query = [&](int p) {
    int res = 0;
    for (p++; p; p -= p & -p) {
      res += fenw[p];
    }
    return res;
  };
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(a[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
  }
  vector<int> L(n);
  for (int i = 0; i < n; i++) {
    L[i] = Query(n - 1) - Query(a[i]);
    Modify(a[i], +1);
  }
  fenw = vector<int>(n + 1, 0);
  vector<int> R(n);
  for (int i = n - 1; i >= 0; i--) {
    R[i] = Query(n - 1) - Query(a[i]);
    Modify(a[i], +1);
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    res += min(L[i], R[i]);
  }
  cout << res << '\n';
  return 0;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:14:13: warning: unused variable 'ans' [-Wunused-variable]
   14 |   long long ans = 1e18;
      |             ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55