Submission #224574

#	Time	Username	Problem	Language	Result	Execution time	Memory
224574		Haunted_Cpp	Mountains (NOI20_mountains)	C++17	100 / 100	213 ms	7548 KiB

Mountains

#include <iostream>
#include <vector>
#include <algorithm>
 
typedef long long i64;
using namespace std;
 
const int N = 3e5 + 5;
 
i64 a [N];

struct FenwickTree {
  vector<int> bit;
  const int N;
  FenwickTree (int n) : N (n + 5) {
    bit.clear(); bit.resize(N);
  }
  void update (int idx, int delta) {
    for (; idx < N; idx += idx & (- idx)) {
      bit[idx] += delta;
    }
  }
  int query (int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & (- idx)) {
      res += bit[idx];
    }
    return res;
  }
  int range_sum (int lo, int hi) {
    return query (hi) - query (lo -1);
  }
};


int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<i64> comp;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    comp.emplace_back(a[i]);
  }
  sort (comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  FenwickTree menor (n), maior (n);
  for (int i = 0; i < n; i++) {
    a[i] = (lower_bound (comp.begin(), comp.end(), a[i]) - comp.begin() + 1);
    maior.update(a[i], +1);
  }
  i64 res = 0;
  for (int i = 0; i < n; i++) {
    maior.update(a[i], -1);
    res += 1LL * menor.range_sum (0, a[i] - 1) * maior.range_sum (0, a[i] - 1);
    menor.update(a[i], +1);
  }
  cout << res << '\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