Submission #1245659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245659		lopkus	Mountains (NOI20_mountains)	C++20	2 / 100	60 ms	5208 KiB

Mountains

#include <bits/stdc++.h>

#define int64_t int

const int N = 3e5 + 5;

struct fenwick {
  int t[N];
  int query(int i) {
    int ans = 0;
    for(; i > 0; i -= i & - i) {
      ans += t[i];
    }
    return ans;
  }
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
  void update(int i, int v) {
    for(; i < N; i += i & - i) {
      t[i] += v;
    }
  }
  void update(int l, int r, int v) {
    update(l, v);
    update(r + 1, - v);
  }
}fenwick;

signed main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> compres;
  for(int i = 1; i <= n; i++) {
    compres.push_back(a[i]);
  }
  std::sort(compres.begin(), compres.end());
  compres.erase(unique(compres.begin(), compres.end()), compres.end());
  for(int i = 1; i <= n; i++) {
    a[i] = lower_bound(compres.begin(), compres.end(), a[i]) - compres.begin() + 1;
  }
  int64_t ans = 0;
  std::vector<int> p(n + 1), s(n + 1);
  for(int i = 1; i <= n; i++) {
    p[i] = fenwick.query(a[i] - 1);
    fenwick.update(a[i], 1);
  }
  for(int i = 1; i <= n; i++) {
    fenwick.update(a[i], - 1);
  }
  for(int i = n; i >= 1; i--) {
    s[i] = fenwick.query(a[i] - 1);
    fenwick.update(a[i], 1);
  }
  for(int i = 1; i <= n; i++) {
    ans += p[i] * s[i];
  }
  std::cout << ans;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12