oj.uz

Submission #895376

# Submission time Handle Problem Language Result Execution time Memory
895376 2023-12-29T20:05:01 Z MilosMilutinovic 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 85 ms 9332 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2016 KB Output is correct
2 Correct 31 ms 3380 KB Output is correct
3 Correct 49 ms 4812 KB Output is correct
4 Correct 67 ms 6448 KB Output is correct
5 Correct 40 ms 6360 KB Output is correct
6 Correct 22 ms 3280 KB Output is correct
7 Correct 49 ms 6976 KB Output is correct
8 Correct 81 ms 9304 KB Output is correct
9 Correct 82 ms 9332 KB Output is correct
10 Correct 85 ms 9296 KB Output is correct