Language: C++

#include <bits/stdc++.h>
using namespace std;

int main () {
  int n, k;
  cin >> n >> k;
  vector<int> arr(n);
  vector<int> m_arr(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    arr[i] = x;
    m_arr[i] = -x;
  }
  sort(arr.begin(), arr.end());
  sort(m_arr.begin(), m_arr.end());

  long long ok = - 1e18;
  long long ng = 1e18 + 1;

  while (ng - ok > 1) {
    long long mid = (ok + ng) / 2;
    long long smaller = 0;
    long long smaller_or_same = 0;

    for (int i = 0; i < n; ++i) {
      int a = arr[i];
      if (a > 0) {
        long long b = mid / a;
        smaller_or_same += max(0, distance(arr.begin(), upper_bound(arr.begin(), arr.end(), b)) - (i + 1));
        if (mid % a != 0) {
          b += 1;
        }
        smaller += max(0, distance(arr.begin(), lower_bound(arr.begin(), arr.end(), b)) - (i + 1));
      }
      if (a < 0) {
        long long b = mid / (-a);
        smaller_or_same += min(n - (i + 1), distance(m_arr.begin(), upper_bound(m_arr.begin(), m_arr.end(), b)));
        if (mid % (-a) != 0) {
          b += 1;
        }
        smaller += min(n - (i + 1), distance(m_arr.begin(), lower_bound(m_arr.begin(), m_arr.end(), b)));
      }
      if (a == 0) {
        if (mid >= 0) {
          smaller_or_same += n - (i + 1);
        }
        if (mid > 0) {
          smaller += n - (i + 1);
        }
      }
    }
    if (smaller < k && k <= smaller_or_same) {
      cout << mid << endl;
      return 0;
    } else if (smaller_or_same < k) {
      ok = mid + 1;
    } else {
      ng = mid;
    }
  }
  cout << ok << endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:30:31: error: no matching function for call to 'max(int, std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type)'
   30 |         smaller_or_same += max(0, distance(arr.begin(), upper_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:30:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'})
   30 |         smaller_or_same += max(0, distance(arr.begin(), upper_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:30:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   30 |         smaller_or_same += max(0, distance(arr.begin(), upper_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:34:23: error: no matching function for call to 'max(int, std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type)'
   34 |         smaller += max(0, distance(arr.begin(), lower_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:34:23: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'})
   34 |         smaller += max(0, distance(arr.begin(), lower_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:34:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   34 |         smaller += max(0, distance(arr.begin(), lower_bound(arr.begin(), arr.end(), b)) - (i + 1));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:38:31: error: no matching function for call to 'min(int, std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type)'
   38 |         smaller_or_same += min(n - (i + 1), distance(m_arr.begin(), upper_bound(m_arr.begin(), m_arr.end(), b)));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:38:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'})
   38 |         smaller_or_same += min(n - (i + 1), distance(m_arr.begin(), upper_bound(m_arr.begin(), m_arr.end(), b)));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:38:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   38 |         smaller_or_same += min(n - (i + 1), distance(m_arr.begin(), upper_bound(m_arr.begin(), m_arr.end(), b)));
      |                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:42:23: error: no matching function for call to 'min(int, std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type)'
   42 |         smaller += min(n - (i + 1), distance(m_arr.begin(), lower_bound(m_arr.begin(), m_arr.end(), b)));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:42:23: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'})
   42 |         smaller += min(n - (i + 1), distance(m_arr.begin(), lower_bound(m_arr.begin(), m_arr.end(), b)));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:42:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   42 |         smaller += min(n - (i + 1), distance(m_arr.begin(), lower_bound(m_arr.begin(), m_arr.end(), b)));
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~