Simple Binary-Search O(NlogA) Solution [C++]
Since It\'s really confusing that you tackle this problem without division into cases, you\'d be better determine the sign of number at first.\n\nAt first, I tr
Since It\'s really confusing that you tackle this problem without division into cases, you\'d be better determine the sign of number at first.\n\nAt first, I tried O(NlogNlogA) Soluiton, but it was too slow to finish in TL.\n\nHere\'s my implemention in C++.\n\nTime Complexity : O(NlogA)\nSpace Complexity : O(N)\n\n```\ntypedef long long ll;\n\ntemplate<class T = int>int bisect_right(const std::vector<T> & V, T val){if (V.size() == 0){return 0;}auto it = upper_bound(V.begin(), V.end(), val);int index = it - V.begin();return index;}\n\nclass Solution {\npublic:\n    long long kthSmallestProduct(vector<int>& arr1, vector<int>& arr2, long long k){\n        vector<vector<ll>> nums1(3);\n        vector<vector<ll>> nums2(3);\n\n        const int n1 = arr1.size();\n        const int n2 = arr2.size();\n\n        for (auto & e : arr1){\n            if (e > 0){\n                nums1[0].emplace_back(e);\n            }else if (e == 0){\n                nums1[1].emplace_back(e);    \n            }else{\n                nums1[2].emplace_back(-e);\n            }\n        }\n        reverse(nums1[2].begin(), nums1[2].end());\n\n        for (auto & e : arr2){\n            if (e > 0){\n                nums2[0].emplace_back(e);\n            }else if (e == 0){\n                nums2[1].emplace_back(e);    \n            }else{\n                nums2[2].emplace_back(-e);\n            }\n        }\n        reverse(nums2[2].begin(), nums2[2].end());\n\n        auto count_not_less_than = [&](ll x){\n            ll res = 0;\n            if (x < 0){\n                res += 1ll * nums1[2].size() * nums2[0].size();\n                res += 1ll * nums1[0].size() * nums2[2].size();\n                res -= countNoLessThan(nums1[2], nums2[0], -x - 1);\n                res -= countNoLessThan(nums1[0], nums2[2], -x - 1);\n                // for (auto & e : nums1[2]){\n                //     res -= bisect_right<ll>(nums2[0], (-x - 1) / e);\n                // }\n                // for (auto & e : nums1[0]){\n                //     res -= bisect_right<ll>(nums2[2], (-x - 1) / e);\n                // }\n            }else if (x == 0){\n                res += 1ll * n1 * n2;\n                res -= 1ll * nums1[0].size() * nums2[0].size();\n                res -= 1ll * nums1[2].size() * nums2[2].size();\n            }else if (x > 0){\n                res += 1ll * n1 * n2;\n                res -= 1ll * nums1[0].size() * nums2[0].size();\n                res -= 1ll * nums1[2].size() * nums2[2].size();\n                res += countNoLessThan(nums1[2], nums2[2], x);\n                res += countNoLessThan(nums1[0], nums2[0], x);\n                // for (auto & e : nums1[2]){\n                //     res += bisect_right<ll>(nums2[2], x / e);\n                // }\n                // for (auto & e : nums1[0]){\n                //     res += bisect_right<ll>(nums2[0], x / e);\n                // }\n            }\n            return res;\n        };\n        \n        ll ng = -1e10 - 1, ok = 1e10 + 1;\n        while(ok - ng > 1){\n            ll mid = (ng + ok) / 2;\n            if (count_not_less_than(mid) < k){\n                ng = mid;\n            }else{\n                ok = mid;\n            }\n        }\n        return ok;\n    }\n    long long countNoLessThan(vector<ll>& arr1, vector<ll>& arr2, long long k){\n        //assume both array are sorted.\n        const int n1 = arr1.size();\n        const int n2 = arr2.size();\n        ll res = 0;\n        for (int i = n1 - 1, ptr = 0; i >= 0; i--){\n            while(ptr < n2 && arr2[ptr] <=  k / arr1[i]){\n                ptr++;\n            }\n            res += ptr;\n        }\n        return res;\n    }\n};\n```
['Binary Tree']