Binary Search + Greedy. Different from any other solution in the community. Beating 75% in speed.
Approach\nCreate a tuple of length 5 such that binary search can be operated upon.\nThe meaning:\n1: first element;\n2: second element;\n3: the max first elemen
# Approach\nCreate a tuple of length 5 such that binary search can be operated upon.\nThe meaning:\n1: first element;\n2: second element;\n3: the max first element to the right;\n4: the max second element to the right;\n\nget a vector that contains the tuples created from `nums1` and `nums2`. sort the vector.\n\nWe would like to search from the very end of the vector. Because that\'s where the sum is the biggest. And stop whenever there is a tuple the matches the criteria. (greedy).\n\nThat will be too slow, though. That\'s when the 3rd and 4th elements comes into play.\n\nSo instead of searching starting from the very end. use the 3rd and 4th elements to rule out the obviously unmatched elements to the right end of the array. (because if the max of the first elements to the right of me is still smaller than the first element of the query, than I shouldn\'t look right any more. Same with the second element, too).\n\nwould like to do ( but slow ):\n---------> sum increase\n[][][][][][][][][][][][][][][][][][][][][][][][][][]\n<--------------search <------------------\n\noptimisation mechanism:\n---------> sum increase\n[][][][][][][]["start search from me. Right ones have small values in nums1 or nums2"][][][][][][][][][][][][][][][][][][]\n\noptimisation:\n---------> sum increase\n[][][][][][][][][skipped]......\nsearch <---\n\n\n# Complexity\n- Time complexity: $O(n\\log(n))$ (amortised?)\n\n- Space complexity: $O(n)$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<int> res;\n        // meaning of sum_arr:\n        // 0: sum of two; 1: first element; 2: second element; 3: the max first element to the right; 4: the max second elemnt to the right\n        vector<tuple<int,int,int,int,int>> sum_arr;\n        for(int i = 0; i < nums1.size(); ++i) {\n            sum_arr.emplace_back(tuple<int,int,int,int,int>{nums1[i] + nums2[i], nums1[i], nums2[i], nums1[i], nums2[i]});\n        }\n        // search should start from the biggest sum end going to the smallest sum end. Whenever a tuple fits, break the loop and that\'s the tuple we want. (greedy)\n        sort(sum_arr.begin(), sum_arr.end());\n        \n        // Fill in the 3rd and 4th elements of the tuples.\n        if (sum_arr.size() > 1 )\n            for(auto it = sum_arr.rbegin() + 1; it != sum_arr.rend(); ++it) {\n                get<3>(*it) = max(get<3>(*it), get<3>(*(prev(it))));\n                get<4>(*it) = max(get<4>(*it), get<4>(*(prev(it))));\n            }\n            \n        for(int i = 0; i < queries.size(); ++i) {\n            auto[ bit, eit ] = equal_range(\n                sum_arr.begin(), sum_arr.end(), tuple<int,int,int,int,int>{queries[i][0] + queries[i][1], queries[i][0], queries[i][1], queries[i][0], queries[i][1]}\n            );\n\n            // !!!!!!! key: We should start not from the very end (with the biggest sum). \n            //              But from a place where at least max(first elements to the right) > first element of query and max(seconds elements to the right ) > second element of query\n            auto start_it = min(\n                lower_bound(sum_arr.begin(), sum_arr.end(), tuple<int,int,int,int,int>{0, 0, 0, queries[i][0], 0}, [](const auto& tp1, const auto& tp2){ return get<3>(tp1) >= get<3>(tp2);}),\n                lower_bound(sum_arr.begin(), sum_arr.end(), tuple<int,int,int,int,int>{0, 0, 0, 0, queries[i][1]}, [](const auto& tp1, const auto& tp2){ return get<4>(tp1) >= get<4>(tp2);})\n            );\n            \n            // the index to start the search, going left. (because the first (or second) elements to the right are all smaller than the first (or second) element of query)\n            start_it = min( next(start_it), prev(sum_arr.end()) );\n            if( eit == bit ) {\n                if(bit == sum_arr.end()) {\n                    res.push_back(-1);\n                    continue;\n                } else {\n                    bool flag = false;\n                    for(int j = start_it - sum_arr.begin(); j >= bit - sum_arr.begin(); --j) {\n                        if(get<1>(sum_arr[j]) >= queries[i][0] && get<2>(sum_arr[j]) >= queries[i][1]) {\n                            res.push_back(get<0>(sum_arr[j]));\n                            flag = true;\n                            break;\n                        }\n                    }\n                    if(!flag)\n                        res.push_back(-1);\n                }            \n            } else {\n                bool flag = false;\n                for(int j = start_it - sum_arr.begin(); j >= bit - sum_arr.begin(); --j) {\n                    if(get<1>(sum_arr[j]) >= queries[i][0] && get<2>(sum_arr[j]) >= queries[i][1]) {\n                        res.push_back(get<0>(sum_arr[j]));\n                        flag = true;\n                        break;\n                    }\n                }\n                if(!flag)\n                    res.push_back(-1);\n            }\n        }\n        return res;\n    }\n};\n```
['C++']