Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)
def run():
    N, K, *A = list(map(int, read().split()))
    B = []
    C = []
    C_abs = []
    O = 0
    for a in A:
        if a == 0:
            O += 1
            continue
        if a > 0:
            B.append(a)
            continue
        C.append(a)
        C_abs.append(-a)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                ret += upper_bound(C, x, b)

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_val = 0
            for i, b in enumerate(B):
                b_val += upper_bound(B[i+1:], x, b)

            c_val = 0
            for i, c in enumerate(C_abs):
                c_val += upper_bound(C_abs[i+1:], x, c)
            ret += (b_val + c_val)
        return ret

    def upper_bound(arr, x, prod):
        low = 0
        high = len(arr)
        if arr == []:
            return 0
        if arr[0] * prod > x:
            return 0
        while high - low > 1:
            current = (high + low) // 2
            tmp = arr[current] * prod
            if tmp > x:
                high = current
            if tmp <= x:
                low = current

        return high



    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        if tmp >= K:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))

    c = [[] for _ in range(3)]

    for ai in a:
        if ai < 0:
            c[0].append(ai)
        elif ai == 0:
            c[1].append(ai)
        elif ai > 0:
            c[2].append(ai)

    c[0].sort()
    c[2].sort()

    c0 = len(c[0])
    c1 = len(c[1])
    c2 = len(c[2])

    index = [c0 * c2, c1 * (c0 + c2) + c1 * (c1 - 1) // 2, c0 * (c0 - 1) // 2 + c2 * (c2 - 1) // 2]

    if 0 <= k - 1 < index[0]:
        tmp = [i * j for i in c[0] for j in c[2]]
        tmp.sort()
        print(tmp[k - 1])
    elif index[0] <= k - 1 < index[0] + index[1]:
        print(0)
    elif index[0] + index[1] <= k - 1 < index[0] + index[1] + index[2]:
        tmp = [c[0][i] * c[0][j] for i in range(c0) for j in range(i + 1, c0)] + [c[2][i] * c[2][j] for i in range(c2) for j in range(i + 1, c2)]
        tmp.sort()
        print(tmp[k - index[0] - index[1] - 1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))

    c = [[] for _ in range(3)]

    for ai in a:
        if ai < 0:
            c[0].append(ai)
        elif ai == 0:
            c[1].append(ai)
        elif ai > 0:
            c[2].append(ai)

    c0 = len(c[0])
    c1 = len(c[1])
    c2 = len(c[2])

    index = [c0 * c2, c1 * (c0 + c2) + c1 * (c1 - 1) // 2, c0 * (c0 - 1) // 2 + c2 * (c2 - 1) // 2]

    if 0 <= k - 1 < index[0]:
        tmp = sorted([i * j for i in c[0] for j in c[2]])
        print(tmp[k - 1])
    elif index[0] <= k - 1 < index[0] + index[1]:
        print(0)
    elif index[0] + index[1] <= k - 1 < index[0] + index[1] + index[2]:
        tmp = sorted([c[0][i] * c[0][j] for i in range(c0) for j in range(i + 1, c0)] + [c[2][i] * c[2][j] for i in range(c2) for j in range(i + 1, c2)])
        print(tmp[k - index[0] - index[1] - 1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    while l_i < len(left) and r_i < len(right):
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged


def main():
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))

    c = [[] for _ in range(3)]

    for ai in a:
        if ai < 0:
            c[0].append(ai)
        elif ai == 0:
            c[1].append(ai)
        elif ai > 0:
            c[2].append(ai)

    c0 = len(c[0])
    c1 = len(c[1])
    c2 = len(c[2])

    index = [c0 * c2, c1 * (c0 + c2) + c1 * (c1 - 1) // 2, c0 * (c0 - 1) // 2 + c2 * (c2 - 1) // 2]

    if 0 <= k - 1 < index[0]:
        tmp = []
        for i in c[0]:
            for j in c[2]:
                tmp.append(i * j)
        tmp = merge_sort(tmp)
        print(tmp[k - 1])
    elif index[0] <= k - 1 < index[0] + index[1]:
        print(0)
    elif index[0] + index[1] <= k - 1 < index[0] + index[1] + index[2]:
        tmp = []
        for i in range(c0):
            for j in range(i + 1, c0):
                tmp.append(c[0][i] * c[0][j])
        for i in range(c2):
            for j in range(i + 1, c2):
                tmp.append(c[2][i] * c[2][j])
        tmp = merge_sort(tmp)
        print(tmp[k - index[0] - index[1] - 1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n, k = map(int, input().split())
a = list(map(int, input().split()))
re = sorted(i[0]*i[1] for i in list(combinations(a, 2)))
print(re[k-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))

ans = []

for i in range(n-1):
    for j in range(i+1, n):
        ans.append(a[i]*a[j])

ans.sort()
print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
INF=10**18+1
l=-INF
r=INF

def condition(x):
    tot=0
    for i in range(n):
        if(a[i]<0):
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    rr=xx
                else:
                    ll=xx
            tot+=n-rr
        else:
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    ll=xx
                else:
                    rr=xx
            tot+=rr
        if(a[i]*a[i]<x):tot-=1
    tot//=2
    return tot<k

while(l+1<r):
    x=(l+r)//2
    if(condition(x)):l=x
    else:r=x
print(l)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
print(sorted([i*j for i,j in list(itertools.combinations(a,2))])[k-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def calc(x):
    sum = 0
    
    for i in range(n):
        if a[i] < 0:
            l,r = n,-1
            while abs(r-l) > 1:
                c = abs(r + l) // 2
                if a[c] * a[i] <= x:
                    l = c
                else:
                    r = c
            sum += n- l

        else:
            l,r = -1,n
            while r-l > 1:
                c = (r + l) // 2
                if a[c] * a[i] <= x:
                    l = c
                else:
                    r = c
            sum += l+1

        if a[i]*a[i] <= x : sum -= 1

    return sum // 2

r = 10 ** 18 +1
l = -r

while r - l > 1:
    x = (r + l) // 2
    if calc(x) >= k:  
        r = x
    else:             
        l = x
print(r)

Submission status: Time Limit Exceeded

Solution code:
# n,m=map(int,input().split())
# n = int(input())
# b = list(map(int,input().split()))
# l = [list(map(int,input().split())) for _ in range(m)]
import numpy as np
import copy
from bisect import bisect_right,bisect_left


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def calc(x):
    sum = 0
    
    for i in range(n):
        if a[i] < 0:
            l,r = n,-1
            while abs(r-l) > 1:
                c = abs(r + l) // 2
                if a[c] * a[i] <= x:
                    l = c
                else:
                    r = c
            sum += n- l

        else:
            l,r = -1,n
            while r-l > 1:
                c = (r + l) // 2
                if a[c] * a[i] <= x:
                    l = c
                else:
                    r = c
            sum += l+1

        if a[i]*a[i] <= x : sum -= 1

    return sum // 2

r = 10 ** 18 +1
l = -r

while r - l > 1:
    x = (r + l) // 2
    if calc(x) >= k:  
        r = x
    else:             
        l = x
print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)


# 答えが負の場合
if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2

        or_higher_cnt = 0
        r = positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

# 答えが正の場合
else:
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).



def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # target 以下の個数を求める
            cnt += bisect_right(L_negative, target)
            # 定数倍高速化
            if cnt >= k:
                return True
        return False    


    # def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
    #     pos_cnt = 0
    #     if len(L_positive) >= 2:
    #         for num in L_positive:
    #             target = pivot // num
    #             # target 以下の個数を求める
    #             pos_cnt += bisect_right(L_positive, target)
    #             if num ** 2 <= pivot:
    #                 pos_cnt -= 1
    #         assert(pos_cnt % 2 == 0)
    #         pos_cnt //= 2
    #     # 定数倍高速化
    #     if pos_cnt >= k:
    #         return True
    #     neg_cnt = 0
    #     if len(L_negative) >= 2:
    #         for num in L_negative:
    #             target = pivot // num
    #             # target 以下の個数を求める
    #             neg_cnt += bisect_right(L_negative, target)
    #             if num ** 2 <= pivot:
    #                 neg_cnt -= 1
    #         assert(neg_cnt % 2 == 0)
    #         neg_cnt //= 2
    #     cnt = pos_cnt + neg_cnt
    #     print(f"B pivot {pivot} cnt {cnt} k {k}")
    #     return cnt >= k

    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        cnt = 0
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                tmp = bisect_right(L_positive, target)
                if num ** 2 <= pivot:
                    tmp -= 1
                cnt += (tmp / 2)    # 小数になることもあるが辻褄は最終的に合う
                # 定数倍高速化
                if cnt >= k:
                    return True
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                tmp = bisect_right(L_negative, target)
                if num ** 2 <= pivot:
                    tmp -= 1
                cnt += (tmp / 2)
                if cnt >= k:
                    return True
        return False

    n, k = mi()
    L = lmi()
    L.sort()
    l_z = bisect_left(L, 0)
    r_z = bisect_right(L, 0)
    L_negative, L_zero, L_positive = L[:l_z], L[l_z:r_z], L[r_z:]

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))
    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).



def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # target 以下の個数を求める
            cnt += bisect_right(L_negative, target)
            # print(f"A pivot {pivot} cnt {cnt} k {k}")
            # 定数倍高速化
            if cnt >= k:
                return True
        return False    


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                pos_cnt += bisect_right(L_positive, target)
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            assert(pos_cnt % 2 == 0)
            pos_cnt //= 2
        # 定数倍高速化
        if pos_cnt >= k:
            return True
        neg_cnt = 0
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                neg_cnt += bisect_right(L_negative, target)
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            assert(neg_cnt % 2 == 0)
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"B pivot {pivot} cnt {cnt} k {k}")
        return cnt >= k

    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))

    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]        
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    # import time
    # s = time.time()
    main()
    # print(f"elapsed {time.time() - s} sec" )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).



def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # target 以下の個数を求める
            cnt += bisect_right(L_negative, target)
            # 定数倍高速化
            if cnt >= k:
                return True
        return False    


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                pos_cnt += bisect_right(L_positive, target)
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            assert(pos_cnt % 2 == 0)
            pos_cnt //= 2
        # 定数倍高速化
        if pos_cnt >= k:
            return True
        neg_cnt = 0
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                neg_cnt += bisect_right(L_negative, target)
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            assert(neg_cnt % 2 == 0)
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"pivot {pivot} cnt {cnt}")
        return cnt >= k

    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))

    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]        
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    
    if k <= len(L_negative) * len(L_positive):
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        left = - 10 ** 18 - 1
        right = 0
        def is_ok(pivot):
            cnt = 0
            for positive_num in L_positive:
                target = pivot // positive_num
                # target 以下の個数を求める
                cnt += bisect_right(L_negative, target)
            return cnt >= k
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= len(L_negative) * len(L_positive) + len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero)):
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (len(L_negative) * len(L_positive) + len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero)))
        left = 0
        right = 10 ** 18 + 1
        L_negative = [- elm for elm in reversed(L_negative)]       
        def is_ok_handle_duplicate(pivot):
            pos_cnt = 0
            if len(L_positive) >= 2:
                for num in L_positive:
                    target = pivot // num
                    # target 以下の個数を求める
                    pos_cnt += bisect_right(L_positive, target)
                    if num ** 2 <= pivot:
                        pos_cnt -= 1
                assert(pos_cnt % 2 == 0)
                pos_cnt //= 2
            neg_cnt = 0
            if len(L_negative) >= 2:
                for num in L_negative:
                    target = pivot // num
                    # target 以下の個数を求める
                    neg_cnt += bisect_right(L_negative, target)
                    if num ** 2 <= pivot:
                        neg_cnt -= 1
                assert(neg_cnt % 2 == 0)
                neg_cnt //= 2
            cnt = pos_cnt + neg_cnt
            # print(f"pivot {pivot} cnt {cnt}")
            return cnt >= k
        while right - left > 1:
            # print(f"left {left} right {right}")
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid):
                right = mid
            else:
                left = mid
        print(right)        
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
il = bisect.bisect_left(A, 0)
ir = bisect.bisect_right(A, 0)
Am = [-a for a in A[:il][::-1]]
Ap = A[ir:]
A0 = ir - il


def calc(B, x):
    c = 0
    for i, b in enumerate(B):
        c += bisect.bisect_left(B[i + 1:], x // b + 1)
    return c


def check(x):
    #積がx以下になるような組み合わせの個数がK個以上であればTrue
    if x < 0:
        c = 0
        for a in Am:
            b = (-x - 1) // a + 1
            c += bisect.bisect_left(Ap, b)
        return len(Ap) * len(Am) - c >= K
    elif x == 0:
        return len(Ap) * len(Am) + len(A) * (len(A) - 1) // 2 - (
            len(A) - A0) * (len(A) - A0 - 1) // 2 >= K
    else:
        return len(Ap) * len(Am) + len(A) * (
            len(A) - 1) // 2 - (len(A) - A0) * (len(A) - A0 - 1) // 2 + calc(
                Ap, x) + calc(Am, x) >= K


#答えは[-10^18,10^18]の間
lb = -10**18 - 1
rb = 10**18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)