Language: C++

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using lli=long long;

template<typename T>
class Segtree{
  int nbin;
  T param_def;
  std::vector<T> seg_vec;
  std::function<T(T, T)> seg_func;
  T segtree_query_partial(int a, int b, int k, int l, int r){
    if(r <= a || b <= l) return param_def;
    if(a <= l && r <= b) return seg_vec[k];
    const T v_l = segtree_query_partial(a, b, k*2+1, l, (l+r)/2);
    const T v_r = segtree_query_partial(a, b, k*2+2, (l+r)/2, r);
    return seg_func(v_l, v_r);
  }
  auto max_bit(int32_t n){
    n = n & 0xFFFF0000 ? n & 0xFFFF0000 : n;
    n = n & 0xFF00FF00 ? n & 0xFF00FF00 : n;
    n = n & 0xF0F0F0F0 ? n & 0xF0F0F0F0 : n;
    n = n & 0xCCCCCCCC ? n & 0xCCCCCCCC : n;
    n = n & 0xAAAAAAAA ? n & 0xAAAAAAAA : n;
    return n;
  }
  public:
  Segtree(const int N, const std::function<T(T, T)>& _seg_func, const T _param_def) :
    seg_func(_seg_func), param_def(_param_def) {
      nbin = max_bit(N-1)*2;
      seg_vec.resize(nbin*2-1, param_def);
      auto insert_top = seg_vec.begin();
      insert_top += nbin-1;
      for(int i = nbin-2; i >= 0; i--){
        seg_vec[i] = seg_func(seg_vec[i*2+1], seg_vec[i*2+2]);
      }
    }
  Segtree(const std::vector<T>& data, const std::function<T(T, T)>& _seg_func, const T _param_def) :
    seg_func(_seg_func), param_def(_param_def) {
      nbin = max_bit(data.size()-1)*2;
      seg_vec.resize(nbin*2-1, param_def);
      auto insert_top = seg_vec.begin();
      insert_top += nbin-1;
      std::copy(data.cbegin(), data.cend(), insert_top);
      for(int i = nbin-2; i >= 0; i--){
        seg_vec[i] = seg_func(seg_vec[i*2+1], seg_vec[i*2+2]);
      }
    }
  T get(int i){
    return seg_vec[nbin-1+i];
  }
  void update(int i, int x){
    i += nbin-1;
    seg_vec[i] = x;
    while(i > 0){
      i = (i-1)/2;
      seg_vec[i] = seg_func(seg_vec[i*2+1], seg_vec[i*2+2]);
    }
  }
  T query(int a, int b){
    return segtree_query_partial(a, b, 0, 0, nbin);
  }
};

lli lower_med(const std::vector<lli>& a_arr, lli t){
  Segtree<lli> seg(200005, [](const lli a, const lli b){return a+b;}, 0);
  lli sum = 100001, ans=0;
  seg.update(sum, seg.get(sum)+1);
  for(lli i = 0; i < a_arr.size(); i++){
    if(a_arr[i] <= t) sum--;
    else sum++;
    ans += i+1 - seg.query(0, sum+1);
    seg.update(sum, seg.get(sum)+1);
  }
  return ans;
}

int main(){
  lli N;
  std::cin >> N;

  std::vector<lli> a_arr(N);
  for(lli i = 0; i < N; i++){
    std::cin >> a_arr[i];
  }

  lli n_med_half = (N*(N+1)/2)/2+1;
  lli begin = 0, end = 1000000005;

  while(end-begin>1){
    lli med=(begin+end-1)/2;
    lli lm = lower_med(a_arr, med);
    if(lm >= n_med_half) end=med+1;
    else begin=med+1;
  }

  std::cout << begin << std::endl;

  return 0;
}



Compiler output:
a.cc:13:8: error: 'function' in namespace 'std' does not name a template type
   13 |   std::function<T(T, T)> seg_func;
      |        ^~~~~~~~
a.cc:5:1: note: 'std::function' is defined in header '<functional>'; this is probably fixable by adding '#include <functional>'
    4 | #include <algorithm>
  +++ |+#include <functional>
    5 | 
a.cc:30:35: error: 'function' in namespace 'std' does not name a template type
   30 |   Segtree(const int N, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                                   ^~~~~~~~
a.cc:30:30: note: 'std::function' is defined in header '<functional>'; this is probably fixable by adding '#include <functional>'
   30 |   Segtree(const int N, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                              ^~~
a.cc:30:43: error: expected ',' or '...' before '<' token
   30 |   Segtree(const int N, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                                           ^
a.cc:40:50: error: 'function' in namespace 'std' does not name a template type
   40 |   Segtree(const std::vector<T>& data, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                                                  ^~~~~~~~
a.cc:40:45: note: 'std::function' is defined in header '<functional>'; this is probably fixable by adding '#include <functional>'
   40 |   Segtree(const std::vector<T>& data, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                                             ^~~
a.cc:40:58: error: expected ',' or '...' before '<' token
   40 |   Segtree(const std::vector<T>& data, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |                                                          ^
a.cc: In constructor 'Segtree<T>::Segtree(int, int)':
a.cc:31:5: error: class 'Segtree<T>' does not have any field named 'seg_func'
   31 |     seg_func(_seg_func), param_def(_param_def) {
      |     ^~~~~~~~
a.cc:31:14: error: '_seg_func' was not declared in this scope
   31 |     seg_func(_seg_func), param_def(_param_def) {
      |              ^~~~~~~~~
a.cc:31:36: error: '_param_def' was not declared in this scope; did you mean 'param_def'?
   31 |     seg_func(_seg_func), param_def(_param_def) {
      |                                    ^~~~~~~~~~
      |                                    param_def
a.cc: In constructor 'Segtree<T>::Segtree(const std::vector<T>&, int)':
a.cc:41:5: error: class 'Segtree<T>' does not have any field named 'seg_func'
   41 |     seg_func(_seg_func), param_def(_param_def) {
      |     ^~~~~~~~
a.cc:41:14: error: '_seg_func' was not declared in this scope
   41 |     seg_func(_seg_func), param_def(_param_def) {
      |              ^~~~~~~~~
a.cc:41:36: error: '_param_def' was not declared in this scope; did you mean 'param_def'?
   41 |     seg_func(_seg_func), param_def(_param_def) {
      |                                    ^~~~~~~~~~
      |                                    param_def
a.cc: In function 'lli lower_med(const std::vector<long long int>&, lli)':
a.cc:68:72: error: no matching function for call to 'Segtree<long long int>::Segtree(int, lower_med(const std::vector<long long int>&, lli)::<lambda(lli, lli)>, int)'
   68 |   Segtree<lli> seg(200005, [](const lli a, const lli b){return a+b;}, 0);
      |                                                                        ^
a.cc:40:3: note: candidate: 'Segtree<T>::Segtree(const std::vector<T>&, int) [with T = long long int]'
   40 |   Segtree(const std::vector<T>& data, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |   ^~~~~~~
a.cc:40:3: note:   candidate expects 2 arguments, 3 provided
a.cc:30:3: note: candidate: 'Segtree<T>::Segtree(int, int) [with T = long long int]'
   30 |   Segtree(const int N, const std::function<T(T, T)>& _seg_func, const T _param_def) :
      |   ^~~~~~~
a.cc:30:3: note:   candidate expects 2 arguments, 3 provided
a.cc:9:7: note: candidate: 'Segtree<long long int>::Segtree(const Segtree<long long int>&)'
    9 | class Segtree{
      |       ^~~~~~~
a.cc:9:7: note:   candidate expects 1 argument, 3 provided
a.cc:9:7: note: candidate: 'Segtree<long long int>::Segtree(Segtree<long long int>&&)'
a.cc:9:7: note:   candidate expects 1 argument, 3 provided
a.cc: In instantiation of 'void Segtree<T>::update(int, int) [with T = long long int]':
a.cc:70:13:   required from here
   70 |   seg.update(sum, seg.get(sum)+1);
      |   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:59:28: error: 'seg_func' was not declared in this scope
   59 |       seg_vec[i] = seg_func(seg_vec[i*2+1], seg_vec[i*2+2]);
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc: In instantiation of 'T Segtree<T>::segtree_query_partial(int, int, int, int, int) [with T = long long int]':
a.cc:63:12:   required from 'T Segtree<T>::query(int, int) [with T = long long int]'
   63 |     return segtree_query_partial(a, b, 0, 0, nbin);
      |            ^~~~~~~~~~~~~~~~~~~~~
a.cc:74:27:   required from here
   74 |     ans += i+1 - seg.query(0, sum+1);
      |                  ~~~~~~~~~^~~~~~~~~~
a.cc:19:20: error: 'seg_func' was not declared in this scope
   19 |     return seg_func(v_l, v_r);
      |            ~~~~~~~~^~~~~~~~~~