C++ Binary Search with O((m+n)lg10**10)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <iostream>\n#include <vector>\n#include <chrono>\n#include <limits>\n#include <algorithm>\n\nusing std::vector;\n\nclass Solution {\npublic:\n    long long kthSmallestProduct(vector<int>& left, vector<int>& right, long long k) {\n      long long min = 0l, max = 0l, mid = 0l;\n      if (left[0] > 0) {\n        if (right[0] > 0) {\n          // \u7EAF\u6B63 \u7EAF\u6B63\n          min = static_cast<long long>(left[0]) * static_cast<long long>(right[0]);\n          max = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[right.size()-1]);\n        } else if (right[right.size()-1] <= 0) {\n          // \u7EAF\u6B63 \u7EAF\u8D1F\n          min = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[0]);\n          max = static_cast<long long>(left[0]) * static_cast<long long>(right[right.size()-1]);\n        } else {\n          // \u7EAF\u6B63 \u6DF7\u5408\n          min = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[0]);\n          max = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[right.size()-1]);\n        }\n      } else if (left[left.size()-1] <= 0) {\n        if (right[0] > 0) {\n          // \u7EAF\u8D1F \u7EAF\u6B63\n          min = static_cast<long long>(left[0]) * static_cast<long long>(right[right.size()-1]);\n          max = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[0]);\n        } else if (right[right.size()-1] <= 0) {\n          // \u7EAF\u8D1F \u7EAF\u8D1F\n          min = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[right.size()-1]);\n          max = static_cast<long long>(left[0]) * static_cast<long long>(right[0]);\n        } else {\n          // \u7EAF\u8D1F \u6DF7\u5408\n          min = static_cast<long long>(left[0]) * static_cast<long long>(right[right.size()-1]);\n          max = static_cast<long long>(left[0]) * static_cast<long long>(right[0]);\n        }\n      } else {\n        if (right[0] > 0) {\n          // \u6DF7\u5408 \u7EAF\u6B63\n          min = static_cast<long long>(left[0]) * static_cast<long long>(right[right.size()-1]);\n          max = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[right.size()-1]);\n        } else if (right[right.size()-1] <= 0) {\n          // \u6DF7\u5408 \u7EAF\u8D1F\n          min = static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[0]);\n          max = static_cast<long long>(left[0]) * static_cast<long long>(right[0]);\n        } else {\n          // \u6DF7\u5408 \u6DF7\u5408\n          min = std::min(left[0] * static_cast<long long>(right[right.size()-1]), static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[0]));\n          max = std::max(left[0] * static_cast<long long>(right[0]), static_cast<long long>(left[left.size()-1]) * static_cast<long long>(right[right.size()-1]));\n        }\n      }\n\n      auto findLastNegative = [](vector<int>& nums) -> const int {\n        int i = 0;\n        for (; i < nums.size(); i++) {\n          if (nums[i] >= 0) {\n            return i-1;\n          }\n        }\n        return nums.size()-1;\n      };\n      auto findFirstPositive = [](vector<int>& nums) -> const int {\n        int i = 0;\n        for (; i < nums.size(); i++) {\n          if (nums[i] > 0) {\n            return i;\n          }\n        }\n        return nums.size();\n      };\n\n      int lx = findLastNegative(left);\n      int ly = findFirstPositive(left);\n      int rx = findLastNegative(right);\n      int ry = findFirstPositive(right);\n\n      while (true) {\n        if (max - min <= 1) {\n          if (find(left, right, min, lx, ly, rx, ry) >= k) {\n            return min;\n          } else {\n            return max;\n          }\n        }\n\n        mid = (min+max)/2;\n        if (find(left, right, mid, lx, ly, rx, ry) < k) {\n          min = mid;\n        } else {\n          max = mid;\n        }\n      }\n      return mid;\n    }\n\n    long long find(vector<int>& left, vector<int>& right, long long target, int lx, int ly, int rx, int ry) {\n      long long k = 0;\n      if (target >= 0l) {\n        // -8, -4, -2, -1, 0, 1, 2, 4, 8 -> 3, 5\n        // -8, -4, -2, -1, 0, 1, 2, 4, 8 -> 3, 5\n        k += static_cast<long long>(lx+1)*static_cast<long long>((right.size()-ry));      // left \u7684\u8D1F\u6570 * right \u7684\u6B63\u6570\n        k += static_cast<long long>(left.size()-ly)*static_cast<long long>((rx+1));       // left \u7684\u6B63\u6570 * right \u7684\u8D1F\u6570\n        k += static_cast<long long>(ly-lx-1)*static_cast<long long>(right.size());        // left \u7684\u96F6 * right\n        k += static_cast<long long>(ry-rx-1)*static_cast<long long>(left.size());         // right \u7684\u96F6 * left\n        k -= static_cast<long long>(ly-lx-1)*static_cast<long long>((ry-rx-1));           // left \u7684\u96F6 * right \u7684\u96F6\n\n        int i = 0, j = rx;\n        // -8, -4, -2, -1\n        // -8, -4, -2, -1\n        for (; i <= lx; i++) {\n          // j \u662F\u4ECE\u53F3\u5F80\u5DE6\u7B2C\u4E00\u4E2A\u4E0D\u6EE1\u8DB3\u7684\u8D1F\u6570\n          while (j >= 0) {\n            long long d = static_cast<long long>(left[i]) * static_cast<long long>(right[j]);\n            if (d <= target) {\n              j--;\n            } else {\n              break;\n            }\n          }\n          k += static_cast<long long>(rx-j);\n        }\n\n        // 1, 2, 4, 8 -> 3,5\n        // 1, 2, 4, 8 -> 3,5\n        j = right.size()-1;\n        for (i = ly; i < left.size(); i++) {\n          // j \u662F\u4ECE\u53F3\u5F80\u5DE6, \u6700\u540E\u4E00\u4E2A\u6EE1\u8DB3\u7684\n          while (j >= ry) {\n            long long d = static_cast<long long>(left[i]) * static_cast<long long>(right[j]);\n            if (d > target) {\n              j--;\n            } else {\n              break;\n            }\n          }\n          k += static_cast<long long>(j-ry+1);\n        }\n      } else {\n        int i = 0, j = ry;\n        // -8, -4, -2, -1 -> 3,5\n        // 1, 2, 4, 8 -> 3,5\n        for (; i <= lx; i++) {\n          // j \u662F\u4ECE\u5DE6\u5F80\u53F3, \u7B2C\u4E00\u4E2A\u6EE1\u8DB3\u7684\n          while (j < right.size()) {\n            long long d = static_cast<long long>(left[i]) * static_cast<long long>(right[j]);\n            if (d > target) {\n              j++;\n            } else {\n              break;\n            }\n          }\n          k += static_cast<long long>(right.size()-j);\n        }\n\n        // 1, 2, 3, 4\n        // -8,-4,-2,-1\n        j = 0;\n        for(i = ly; i < left.size(); i++) {\n          // j \u4ECE\u5DE6\u5F80\u53F3, \u7B2C\u4E00\u4E2A\u4E0D\u6EE1\u8DB3\u7684\n          while (j <= rx) {\n            long long d = static_cast<long long>(left[i]) * static_cast<long long>(right[j]);\n            if (d <= target) {\n              j++;\n            } else {\n              break;\n            }\n          }\n          k += static_cast<long long>(j);\n        }\n      }\n\n      return k;\n    }\n\n    int countLess(vector<int>& right, int curr, int target) {\n      for (; curr >= 0; curr--) {\n        if (right[curr] <= target) {\n          return curr;\n        }\n      }\n      return -1;\n    }\n\n    int countGreater(vector<int>& right, int curr, int target) {\n      for (; curr >= 0; curr--) {\n        if (right[curr] < target) {\n          return curr+1;\n        }\n      }\n      return right.size();\n    }\n};\n\n```
['C++']