C++ | Segment Tree | Sorting
Code\n\n\nclass SegTree{\n    vector<int> tree;\npublic:\n\n    SegTree(int n)\n    {\n        tree.resize(4*n, 0);\n    }\n\n    void update(int ind, int val, 
# Code\n```\n\nclass SegTree{\n    vector<int> tree;\npublic:\n\n    SegTree(int n)\n    {\n        tree.resize(4*n, 0);\n    }\n\n    void update(int ind, int val, int l, int r, int i)\n    {\n        if(l == r)\n        {\n            tree[i] = val;\n            return;\n        }\n        int m = (l+r)/2;\n\n        if(m >= ind)\n        {\n            update(ind, val, l, m, 2*i+1);\n        }\n        else\n            update(ind, val, m+1, r, 2*i+2);\n        \n        tree[i] = max(tree[2*i+1], tree[2*i+2]);\n    }\n\n    int query(int x, int y, int l, int r, int i)\n    {\n        if(r<x || l>y)\n            return 0;\n        \n        if(l>=x && r<=y)\n            return tree[i];\n        \n        int m = (l+r)/2;\n        return max(query(x,y,l,m,2*i+1), query(x,y,m+1,r,2*i+2));\n    }\n\n};\n\nclass Solution {\npublic:\n\n    static bool comp(const vector<int>& a, const vector<int>& b)\n    {\n        return a[1] > b[1];\n    }\n\n    static bool comp1(const pair<int, int>& a, const pair<int, int>& b)\n    {\n        return a.first > b.first;\n\n    }\n\n    int find(vector<pair<int, int>>& nums, int k)\n    {\n        int ind = nums.size();\n        int l = 0, r = nums.size()-1;\n\n        while(l<=r)\n        {\n            int mid = (l+r)/2;\n            if(nums[mid].first >= k)\n            {\n                ind = mid;\n                r = mid-1;\n            }\n            else\n                l = mid+1;\n        }\n        return ind;\n    }\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) \n    {\n        int q = queries.size();\n\n        vector<pair<int, int>> nums;\n        for(int i=0;i<nums1.size();i++)\n        {\n            nums.push_back({nums1[i], nums2[i]});\n        }\n        sort(nums.begin(), nums.end());\n        // update nums2 ke basis pe karege aur query nums1 ke basis pe karege\n        for(int i=0;i<q;i++)\n        {\n            queries[i].push_back(i);\n        }\n        sort(queries.begin(), queries.end(), comp);\n\n        vector<pair<int, int>> new_nums2;\n        for(int i=0;i<nums2.size();i++)\n        {\n            int t = nums[i].second;\n            new_nums2.push_back({t, i});\n        }\n        sort(new_nums2.begin(), new_nums2.end(), comp1); // descending order mai sor hoga\n\n        int n = nums.size();\n        SegTree tree(n);\n\n        vector<int> ans(q);\n\n        int i=0;\n        for(auto it: queries)\n        {\n            int pos = it[2];\n            while(i<new_nums2.size())\n            {\n                int val = new_nums2[i].first;\n                int ind = new_nums2[i].second;\n                \n                if(val >= it[1]){\n                    val += nums[ind].first;\n                    tree.update(ind, val, 0, n-1, 0);\n                }\n                else\n                    break;\n                i++;\n            }\n            int x = find(nums, it[0]);\n            if(x<n)\n                ans[pos] = tree.query(x, n-1, 0, n-1, 0);\n            if(ans[pos] == 0)\n                ans[pos] = -1;\n        }\n\n        return ans;\n    }\n};\n```
['C++']