Segment Tree (Ugly Code)
Intuition\n Describe your first thoughts on how to solve this problem. \nSo excited I passed this problem in the last 2 minutes in the contest.\n# Approach\n De
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSo excited I passed this problem in the last 2 minutes in the contest.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: (O(nlogn))\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```\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        n = len(nums1)\n        nums2_sorted = sorted(nums2)\n        nums2_idx_map = dict(zip(nums2_sorted, range(n)))\n        ab = sorted([(a, b) for a, b in zip(nums1, nums2)], reverse=True)\n        queries = sorted([(x, y, i) for i, (x, y) in enumerate(queries)], reverse=True)\n        tree = SegmentTree(n)\n        res = [-1] * len(queries)\n        j = 0\n        for x, y, i in queries:\n            while j < n and ab[j][0] >= x:\n                tree.set(nums2_idx_map[ab[j][1]], ab[j][0] + ab[j][1])\n                j += 1\n            y_idx = bisect.bisect_left(nums2_sorted, y)\n            if y_idx == n:\n                continue\n            else:\n                res[i] = tree.max(y_idx, n)\n        return res\n\n    \nclass SegmentTree:\n    def __init__(self, n):\n        self.size = 1 << (n - 1).bit_length()\n        self.data = [-1] * (2 * self.size)\n\n    def set(self, i, x):\n        i += self.size\n        if self.data[i] >= x:\n            return\n        self.data[i] = x\n        while i > 1:\n            self.data[i >> 1] = max(self.data[i], self.data[i ^ 1])\n            i >>= 1\n\n    def max(self, l, r):\n        l += self.size\n        r += self.size\n        s = -1\n        while l < r:\n            if l & 1:\n                s = max(s, self.data[l])\n                l += 1\n            if r & 1:\n                s = max(s, self.data[r - 1])\n            l >>= 1\n            r >>= 1\n        return s\n        \n```
['Python3']