problem03

//User function Template for C++



class Solution {
public:
    int TotalPairs(vector<int>& nums, int x, int y) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = 0; i < n; i++) {
            int lo = i + 1, hi = n - 1, idx = n;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (nums[i] * nums[mid] >= x) {
                    idx = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            if (idx == n) {
                continue;
            }
            int lo2 = i + 1, hi2 = n - 1, idx2 = -1;
            while (lo2 <= hi2) {
                int mid2 = (lo2 + hi2) / 2;
                if (nums[i] * nums[mid2] > y) {
                    hi2 = mid2 - 1;
                } else {
                    idx2 = mid2;
                    lo2 = mid2 + 1;
                }
            }
            if (idx2 == -1) {
                continue;
            }
            count += (idx2 - idx + 1);
        }
        return count;
    }
};