ABC155 D - Pairs - ferinの競プロ帳

$K$ 番目の数が $X$ 以上か？という判定問題に単調性が存在することから，こうした問題では $K$ 番目の数を決め打つ二分探索を行うのが常套手段です．

「 $K$ 番目の数が $X$ 以上か？」という問題は「 $X$ 未満の数が $K-1$ 個以下か？」と言い換えることができます． $A_i$ を固定したときに $A_iA_j \lt X$ となる $A_j$ が何個存在するかを数えます．

$A_i$ の正負で場合分けしてそれぞれ尺取り法を用いることで数えます．

$A_i \lt 0, A_j \lt 0$
$j$ が大きくなるにつれて $A_iA_j$ は小さくなります．したがって条件を満たす $j$ は区間 $\lbrack k,sz)$ に属します．また， $i$ を大きくした場合 $A_iA_j$ は小さくなるため， $k$ は小さくなる方向に動きます． $i$ に対応する $k$ を保持するように尺取法を行うことで答えを求められます．
$A_i \lt 0, A_j \geq 0$
$A_i \geq 0, A_j \lt 0$
$A_i \geq 0, A_j \geq 0$
他の3パターンについても同様に尺取法で数えられます．

同じ要素を選ぶことはできないことに注意が必要です． $i \lt j$ となるペアだけを数えるのではなく，あとで2で割るようにすると実装が楽です．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, k;  
    cin >> n >> k;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
    sort(ALL(a));  
  
    vector<ll> plus, minus;  
    REP(i, n) {  
        if(a[i]<0) minus.push_back(a[i]);  
        else plus.push_back(a[i]);  
    }  
  
    // K番目がmid以上である → X未満がK-1個以下である  
    auto check = [&](ll x) {  
        ll num = 0;  
        ll idx1 = (ll)minus.size()-1, idx2 = 0;  
        REP(i, minus.size()) {  
            while(idx1 >= 0 && minus[i]*minus[idx1]<x) idx1--;  
            while(idx2 < (ll)plus.size() && minus[i]*plus[idx2]>=x) idx2++;  
            num += (ll)minus.size() - idx1 - 1;  
            if(idx1 < i) num--;  
            num += (ll)plus.size() - idx2;  
        }  
        idx1 = 0, idx2 = (ll)plus.size()-1;  
        REP(i, plus.size()) {  
            while(idx1 < (ll)minus.size() && plus[i]*minus[idx1]<x) idx1++;  
            while(idx2 >= 0 && plus[i]*plus[idx2]>=x) idx2--;  
            num += idx1;  
            num += idx2+1;  
            if(i <= idx2) num--;  
        }  
        return num/2 <= k-1;  
    };  
  
    ll lb = -INF, ub = INF;  
    while(ub-lb>1) {  
        ll mid = (lb+ub)/2;  
        if(check(mid)) lb = mid;  
        else ub = mid;  
    }  
    cout << lb << endl;  
  
    return 0;  
}