Submission #1036245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036245		ind1v	Mountains (NOI20_mountains)	C++11	100 / 100	121 ms	14360 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

struct fenwick_tree {
  int f[N];
  
  fenwick_tree() {
    memset(f, 0, sizeof(f));
  }
  
  void upd(int i, int x) {
    for (; i < N; i += i & -i) {
      f[i] += x;
    }
  }
  
  int get(int i) {
    int r = 0;
    for (; i > 0; i -= i & -i) {
      r += f[i];
    }
    return r;
  }
  
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

int n;
long long H[N];
vector<long long> v;
fenwick_tree ft;
int l[N], r[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> H[i];
  }
  copy(H + 1, H + n + 1, back_inserter(v));
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++) {
    H[i] = lower_bound(v.begin(), v.end(), H[i]) - v.begin() + 1;
  }
  for (int i = 1; i <= n; i++) {
    l[i] = ft.get(H[i] - 1);
    ft.upd(H[i], +1);
  }
  memset(ft.f, 0, sizeof(ft.f));
  for (int i = n; i >= 1; i--) {
    r[i] = ft.get(H[i] - 1);
    ft.upd(H[i], +1);
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += 1LL * l[i] * r[i];
  }
  cout << ans << '\n';
  return 0;
}

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