bench c++

#include <algorithm>
#include <benchmark/benchmark.h>
#include <random>
#include <vector>

using namespace std;

int findMidMax(vector<int> &v, int begin, int end);

int solve(vector<int> &v, int begin, int end) {
  if (begin == end) {
    return 0;
  }
  if (begin + 1 == end) {
    return v[begin];
  }

  int mid = (begin + end) / 2;
  int leftMax = solve(v, begin, mid);
  int rightMax = solve(v, mid, end);
  int midMax = findMidMax(v, begin, end);

  return max(leftMax, max(rightMax, midMax));
}

int findMidMax(vector<int> &v, int begin, int end) {
  int mid = (begin + end) / 2;
  int left = mid - 1;
  int right = mid;
  int minHeight = min(v[left], v[right]);
  int size = 2 * minHeight;
  while (begin < left || right + 1 < end) {
    if (begin < left && (right + 1 == end || v[left - 1] > v[right + 1])) {
      --left;
      minHeight = min(minHeight, v[left]);
    } else {
      ++right;
      minHeight = min(minHeight, v[right]);
    }
    size = max(size, minHeight * (right - left + 1));
  }
  return size;
}

static void Solve(benchmark::State &state) {
  size_t size = state.range(0);
  std::mt19937 gen(12345);
  uniform_int_distribution dist(0, 65535);
  vector<int> s(size);
  generate(begin(s), end(s), [&] { return dist(gen); });
  for (auto _ : state) {
    int res = solve(s, 0, s.size());
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(Solve)
    ->Args({10})
    ->Args({100})
    ->Args({1000})
    ->Args({10000})
    ->Args({100000});

BENCHMARK_MAIN();