Java+sort+treemap (without segment tree).
Intuition\n Describe your first thoughts on how to solve this problem. \nwe sort the nums & queries to make x always follow the rule. \nThen we need to check "x
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe sort the nums & queries to make x always follow the rule. \nThen we need to check "x + y" is max && y >= y\'s requirement.\nHere, the complexity is still O(n^2).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use a treemap to optimize the seach part of y.\nIn our treemap, if (y1 > y2 && sum1 >= sum2), y2 is useless. Because if y2 meets the requirment, y1 also meets, but sum1 is a better answer. So, we need to check ys to two directions. If the higher y1 has a bigger sum, then y itself is uselss. If the lower y1 has a smaller sum, the y1 is uselee.\nFinally, in our treemap, y is in ascending order and sum is in descending order. \n\n# Complexity\n- Time complexity:O(nlgn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {\n        int q2[][] = new int[queries.length][3], ans[] = new int[queries.length];\n        for (int i = 0; i < queries.length; ++i) {\n            q2[i][0] = queries[i][0];\n            q2[i][1] = queries[i][1];\n            q2[i][2] = i;\n        }\n        int nums[][] = new int[nums1.length][2];\n        for (int i = 0; i < nums1.length; ++i) {\n            nums[i][0] = nums1[i];\n            nums[i][1] = nums2[i];\n        }\n        Arrays.sort(nums, (a, b) -> Integer.compare(a[0], b[0]));\n        Arrays.sort(q2, (a, b) -> Integer.compare(a[0], b[0]));\n        // key -> y, value -> x + y\n        // y -> ascend, x + y -> descend\n        TreeMap<Integer, Integer> tm = new TreeMap<>();\n\n        int index = nums.length - 1;\n        for (int i = q2.length - 1; i >= 0; --i) {\n            while (index >= 0 && nums[index][0] >= q2[i][0]) {\n                insert(tm, nums[index][0], nums[index][1]);\n                index--;\n            }\n            var entry = tm.ceilingEntry(q2[i][1]);\n            if (entry == null) ans[q2[i][2]] = -1;\n            else ans[q2[i][2]] = entry.getValue();\n        }\n        return ans;\n    }\n\n    private void insert(TreeMap<Integer, Integer> tm, int x, int y) {\n        int sum = x + y;\n        if (tm.containsKey(y) && tm.get(y) >= sum) return;\n        Integer higher = tm.higherKey(y);\n        if (higher != null && tm.get(higher) >= sum) return;\n        \n        Set<Integer> hs = new HashSet<>();\n        Integer lower = tm.lowerKey(y);\n        while (lower != null) {\n            if (tm.get(lower) <= sum) hs.add(lower);\n            else break;\n            lower = tm.lowerKey(lower);\n        }\n        for (int i : hs) tm.remove(i);\n        tm.put(y, sum);\n    }\n}\n```
['Java']