Submission #299640

#	Time	Username	Problem	Language	Result	Execution time	Memory
299640		zwliew	Mountains (NOI20_mountains)	C++17	100 / 100	1152 ms	27128 KiB

Mountains

#include <algorithm>
#include <array>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <ext/pb_ds/assoc_container.hpp>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// #include "bits/stdc++.h"

using namespace std;

#ifdef LOCAL
#include "../../_library/cc/debug.h"
#define FILE "test"
#else
#define debug(...) 0
#define FILE "cowjog"
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

template <class T>
using OrderStatisticTree =
    __gnu_pbds::tree<T,
                     __gnu_pbds::null_type,
                     less<T>,
                     __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update>;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  if (fopen(FILE ".in", "r")) {
    freopen(FILE ".in", "r", stdin);
    freopen(FILE ".out", "w", stdout);
  }

  // Iterate through each possible middle mountain, and count the number of
  // mountains shorter than the middle mountain on both sides.
  int n;
  cin >> n;
  vector<int64_t> h(n);
  OrderStatisticTree<pair<int64_t, int>> left, right;
  for (int i = 0; i < n; ++i) {
    cin >> h[i];
    right.insert({h[i], i});
  }

  int64_t ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    right.erase(right.lower_bound({h[i], 0}));
    ans +=
        (int64_t)left.order_of_key({h[i], 0}) * right.order_of_key({h[i], 0});
    left.insert({h[i], i});
  }
  cout << ans;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     freopen(FILE ".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     freopen(FILE ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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