Language: C++

#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k; cin>>n>>k;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];

    vector<int> m, p;
    for(int i=0; i<n; i++){
        if(a[i] < 0) m.emplace_back(a[i]);
        else if(a[i] > 0) p.emplace_back(a[i]);
    }

    sort(m.begin(), m.end());
    sort(p.begin(), p.end());

    ll msz = m.size(), psz = p.size();
    int zero = n - msz - psz;

    ll mcnt = msz * psz;

    if(k <= mcnt){
        // k 番目の数がマイナス
        // (ng, ok]
        ll ng = -INF - 1, ok = 0;
        while(ok - ng > 1){
            ll mid = (ng + ok) / 2;
            ll sum = 0;
            int l = 0;
            for(int r=0; r<psz; r++){
                while(l < msz && m[l] * p[r] <= mid) l++;
                sum += l;
            }

            if(sum < k) ng = mid;
            else ok = mid;
        }

        cout << ok << endl;
        return 0;
    }

    k -= mcnt;
    ll zerocnt = 0;
    for(int i=0; i<zero; i++){
        zerocnt += (n - (i + 1));
    }

    if(k <= zerocnt){
        // k 番目の数が 0
        cout << 0 << endl;
        return 0;
    }

    k -= zerocnt;

    for(int i=0; i<msz; i++) m[i] = -m[i];
    sort(m.begin(), m.end());

    // k 番目の数がプラス
    // (ng, ok]
    ll ng = -1, ok = INF;
    while(ok - ng > 1){
        ll mid = (ng + ok) / 2;
        ll sum = 0;
        for(int i=0; i<psz; i++){
            ll target = mid / p[i];
            ll cnt = max(0, (upper_bound(p.begin(), p.end(), target) - p.begin()) - (i + 1));
            sum += cnt;
        }

        for(int i=0; i<msz; i++){
            ll target = mid / m[i];
            ll cnt = max(0, (upper_bound(m.begin(), m.end(), target) - m.begin()) - (i + 1));
            sum += cnt;
        }

        if(sum < k) ng = mid;
        else ok = mid;
    }

    cout << ok << endl;

    return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:113:25: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type)'
  113 |             ll cnt = max(0, (upper_bound(p.begin(), p.end(), target) - p.begin()) - (i + 1));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:2:
/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:113:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
  113 |             ll cnt = max(0, (upper_bound(p.begin(), p.end(), target) - p.begin()) - (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,
                 from a.cc:13:
/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:113:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  113 |             ll cnt = max(0, (upper_bound(p.begin(), p.end(), target) - p.begin()) - (i + 1));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:119:25: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type)'
  119 |             ll cnt = max(0, (upper_bound(m.begin(), m.end(), target) - m.begin()) - (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:119:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
  119 |             ll cnt = max(0, (upper_bound(m.begin(), m.end(), target) - m.begin()) - (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:119:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  119 |             ll cnt = max(0, (upper_bound(m.begin(), m.end(), target) - m.begin()) - (i + 1));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~