Problem p02774 (python)

Fixed submission:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve_negative():
        ok = -1
        ng = -(10 ** 18)
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            count = 0
            for elem_neg in a_neg_desc:
                while pidx < pos_cnt:
                    elem_pos = a_pos_desc[pidx]
                    prod = elem_neg * elem_pos
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += pidx
            if count >= k:
                ok = mid
            else:
                ng = mid

        print(ok)

    def solve_positive():
        kp = k - (prod_neg_cnt + prod_zer_cnt)
        ok = 10 ** 18
        ng = 0
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            nidx = 0
            count = 0
            for i, elem_pos1 in enumerate(a_pos_desc):
                while pidx < pos_cnt:
                    elem_pos2 = a_pos[pidx]
                    prod = elem_pos1 * elem_pos2
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += min(pidx, pos_cnt - (i + 1))

            for i, elem_neg1 in enumerate(a_neg):
                while nidx < neg_cnt:
                    elem_neg2 = a_neg_desc[nidx]
                    prod = elem_neg1 * elem_neg2
                    if prod > mid:
                        break
                    else:
                        nidx += 1
                count += min(nidx, neg_cnt - (i + 1))

            if count >= kp:
                ok = mid
            else:
                ng = mid

        print(ok)

    import bisect
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    neg_cnt = bisect.bisect_left(a, 0)
    zer_cnt = bisect.bisect_left(a, 1) - neg_cnt
    pos_cnt = n - (neg_cnt + zer_cnt)

    prod_neg_cnt = neg_cnt * pos_cnt
    prod_pos_cnt = (neg_cnt * (neg_cnt - 1) + pos_cnt * (pos_cnt - 1)) // 2
    prod_zer_cnt = ((n * (n - 1)) // 2) - (prod_neg_cnt + prod_pos_cnt)

    a_neg = a[:neg_cnt]
    a_pos = a[(n - pos_cnt):]

    if k <= prod_neg_cnt:
        solve_negative()
    elif k <= (prod_neg_cnt + prod_zer_cnt):
        print(0)
    else:
        solve_positive()


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    minus = bisect.bisect_left(a, 0)
    zero = bisect.bisect_left(a, 1) - minus
    plus = n - (minus + zero)

    minus_product = minus * plus
    zero_product = zero * (minus + plus) + ((zero - 1) * zero) // 2

    a_minus = list(map(abs, a[0:minus]))
    a_minus.sort()
    a_plus = a[minus + zero:]

    if k <= minus_product:
        km = k - 1
        a_minus.reverse()
        a_plus.reverse()
        m_absmin = a_minus[-1] * a_plus[-1]
        m_absmax = a_minus[0] * a_plus[0]

        ok = m_absmax
        ng = m_absmin - 1

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            mm = 0
            cnt = 0
            for pp in range(plus):
                mm = 0
                x = a_plus[pp] * a_minus[mm]
                while x > mid:
                    mm += 1
                    x = a_plus[pp] * a_minus[mm]
                cnt += (mm - 1)
            if cnt < km:
                ok = mid
            else:
                ng = mid

        print(-ok)

    elif k <= (minus_product + zero_product):
        print(0)
    else:
        kp = k - (minus_product + zero_product) - 1
        ppmin, pmmin = INF, INF
        ppmax, pmmax = -1, -1
        if plus >= 2:
            ppmin = a_plus[0] * a_plus[1]
            ppmax = a_plus[-1] * a_plus[-2]
        if minus >= 2:
            pmmin = a_minus[0] * a_minus[1]
            pmmax = a_minus[-1] * a_minus[-2]

        p_absmin = min(ppmin, pmmin)
        p_absmax = max(ppmax, pmmax)

        ok = p_absmin
        ng = p_absmax + 1
        mid = (ok + ng) // 2

        while abs(ng - ok) > 1:
            prev_mid = mid
            mid = (ok + ng) // 2
            cnt = 0
            p2 = 0

            for p1 in range(plus):
                p2 = p1 + 1
                while p2 < plus and a_plus[p1] * a_plus[p2] < mid:
                    p2 += 1
                cnt += (p2 - p1 - 1)

            m2 = 0
            for m1 in range(minus):
                m2 = m1 + 1
                while m2 < minus and a_minus[m1] * a_minus[m2] < mid:
                    m2 += 1
                cnt += (m2 - m1 - 1)

            if cnt <= kp:
                ok = mid
            else:
                ng = mid

        print(ok)


if __name__ == '__main__':
    main()