BST + Sweep
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 Add yo
# 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<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Time complexity: $$O(n\\log n)$$\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- Space complexity: $$O(n)$$\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int q = queries.size();\n        vector<int> queries_ord(q);\n        for (int i = 0; i < q; ++i) {\n            queries_ord[i] = i;\n        }\n        sort(begin(queries_ord), end(queries_ord), [&](int i, int j) {\n            return queries[i] > queries[j];\n        });\n        int n = nums1.size();\n        vector<pair<int, int>> points;\n        for (int i = 0; i < n; ++i) {\n            points.emplace_back(nums1[i], nums2[i]);\n        }\n        int current_point = 0;\n        sort(begin(points), end(points), greater<>());\n        vector<int> ans(q, -1);\n        map<int, int> bst; // (y, w) y1 <= y2 => w1 >= w2\n        for (int qi : queries_ord) {\n            int xq = queries[qi][0];\n            int yq = queries[qi][1];\n\n            while (current_point < n && points[current_point].first >= xq) {\n                int x = points[current_point].first;\n                int y = points[current_point].second;\n                ++current_point;\n\n                int w = x + y;\n                auto pos = bst.upper_bound(y);\n                while (pos != bst.begin()) {\n                    pos = prev(pos);\n                    if (pos->second >= w) break;\n                    pos = bst.erase(pos);\n                }\n                pos = bst.upper_bound(y);\n                if (pos == bst.end() || pos-> second < w)\n                    bst.emplace(y, w);\n            }\n\n            auto pos = bst.lower_bound(yq);\n            if (pos != bst.end()) ans[qi] = pos->second;\n        }\n        return ans;\n    }\n};\n```
['Binary Search Tree', 'C++']