Submission #1023172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023172		avighna	Mountains (NOI20_mountains)	C++17	100 / 100	80 ms	11900 KiB

Mountains

#include <bits/stdc++.h>

class FenwickTree {
public:
  std::vector<int> f;
  int n;

  FenwickTree(int n) {
    this->n = n;
    f.resize(n + 1);
  }

  void add(int idx, int del) {
    ++idx;
    for (int i = idx; i <= n; i += i & (-i)) {
      f[i] += del;
    }
  }

  int query(int idx) {
    ++idx;
    int ans = 0;
    for (int i = idx; i >= 1; i -= i & (-i)) {
      ans += f[i];
    }
    return ans;
  }
  int query(int l, int r) {
    if (l > r) {
      return 0;
    }
    int ans = query(r);
    if (l - 1 >= 0) {
      ans -= query(l - 1);
    }
    return ans;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  std::vector<std::pair<long long, int>> h(n);
  FenwickTree tree(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> h[i].first;
    h[i].second = i;
    tree.add(i, 1);
  }
  std::sort(h.begin(), h.end());

  std::stack<int> stk;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    if (i != 0 and h[i].first != h[i - 1].first) {
      while (!stk.empty()) {
        tree.add(stk.top(), -1);
        stk.pop();
      }
    }
    long long left = tree.query(0, h[i].second);
    long long right = tree.query(h[i].second, n - 1);
    // above is >=, so make it <
    ans += (h[i].second - left + 1) * (n - h[i].second - right);
    stk.push(h[i].second);
  }
  std::cout << ans << "\n";
}

• 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