Monotonic stack with binary search | Python
\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        def getSmallestGreater(v
```\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        def getSmallestGreater(value):\n            l=0\n            r=len(mappings)-1\n            ans=len(mappings)\n            while l<=r:\n                m=(l+r)//2\n                if mappings[m][0]==value:\n                    return m\n                elif mappings[m][0]>value:\n                    ans=m\n                    r=m-1\n                else:\n                    l=m+1\n            return ans\n        \n        n=len(nums1)\n        ans=[0]*len(queries)\n        # sort nums1 and nums2 according to nums1\n        pairs=sorted(zip(nums1,nums2))\n        nums1=[x for x,_ in pairs]\n        nums2=[x for _,x in pairs]\n        \n        # sort query indices to process queries in decreasing order of x and use the index to store the answer\n        qindices=[i for i in range(len(queries))]\n        qindices.sort(key=lambda x:queries[x],reverse=True)\n        \n        # mappings is a monotonic stack that will store the mapping [nums2[i] , nums1[i]+nums2[i]] in sorted order with nums2[i] in increasing order and the corresponding values (nums1[i]+nums2[i]) in decreasing order\n        mappings=[]\n        # i is index of element in nums1\n        i=n-1\n        for qidx in qindices:\n            # process all pairs with nums1[i]>=query[qidx][0]\n            while i>-1 and queries[qidx][0]<=nums1[i]:\n                x,y = nums1[i],nums2[i]\n                \n                # case 1 y<=y_top , x+y<= x+y top - discard y,x+y\n                # case 2 y<=y_top , x+y> x+y top - invalid case as x<=x_top and y<=y_top so x+y <= x+y top\n                # case 3 y>y_top , x+y< x+y top - push\n                # case 4 y>y_top , x+y>= x+y top - pop all mappings with x+y>= x+y_top then push\n                \n                # if a mapping is already present with key>=y and value>=x+y, dont store the current element\n                # since a pair already exists such that mapping[key]>=y and its value>=x+y, and since we have sorted nums1,                \n\t\t\t\t# x used in existing mapping is guaranteed to be >= current x\n                if getSmallestGreater(y)<len(mappings) and mappings[getSmallestGreater(y)][1]>=x+y:\n                    i-=1\n                    continue\n                \n                # for all mapping[a] with mapping[a][0]<y and mapping[a][1]<= x+y, delete mapping[a]\n                # this is done to make the mapping values monotonic\n                idx=getSmallestGreater(y)-1\n                while idx<len(mappings) and idx>-1 and mappings[idx][1]<=x+y:\n                    mappings.pop()\n                    idx-=1\n                \n                # insert the current pair mapping\n                mappings.append([y,x+y])\n                    \n                # let si = xi+yi (mapping of yi)\n                # after the above operations, mappings will look like\n                # y1<y2<y3<y4<y5(stack_top)\n                # s1>s2>s3>s4>s5\n                \n                i-=1\n            \n            # get max x+y such that y>=queries[qidx][1]\n            val_idx=getSmallestGreater(queries[qidx][1])\n            if val_idx<len(mappings):\n                ans[qidx]=mappings[val_idx][1]\n            else:\n                ans[qidx]=-1\n        return ans\n```
['Binary Search', 'Sorting', 'Monotonic Stack', 'Binary Tree', 'Python']