seg tree + coord comp + offline queries
Code\n\nlong long INF = 1e14;\n\ntemplate <typename T = int> \nclass SegmentTree {\npublic:\n    \n    vector<T> st; \n    vector<T> arr; \n    int n; \n\t\n\tT
# Code\n```\nlong long INF = 1e14;\n\ntemplate <typename T = int> \nclass SegmentTree {\npublic:\n    \n    vector<T> st; \n    vector<T> arr; \n    int n; \n\t\n\tT invalidValue = -INF;\n    \n\tint left(int ind) {\n\t\treturn 2*ind + 1;\n\t}\n\n\tint right(int ind) {\n\t\treturn 2*ind + 2;\n\t}\n\n\tT operate(T a, T b){\n\t\treturn max(a, b);\n\t}\n\n\tvoid pull(int ind) {\n\t\tst[ind] = operate(st[left(ind)], st[right(ind)]);\n\t}\n\n    \n    void build(int l, int r, int ind){\n        if(l == r){\n            st[ind] = arr[l];\n            return;\n        }\n        \n        int m = (l+r)/2;\n        \n        build(l, m, left(ind));\n        build(m+1, r, right(ind));\n        \n        pull(ind);\n    }\n    \n    T query(int l, int r, int i, int j, int ind){\n        if(l>=i and r<=j){\n            return st[ind];\n        }\n\n        if(r<i or l>j){\n            return invalidValue;\n        }\n        \n        int m = (l+r)/2;\n\n\t\tT leftVal = query(l, m, i, j, left(ind));\n\t\tT rightVal = query(m+1, r, i, j, right(ind));\n\n        return operate(leftVal, rightVal);\n    }\n    \n    void update(int l, int r, T val, int i, int ind){\n\t\tif(l == r){\n\t\t\tif(l == i){\n\t\t\t\tst[ind] = max(st[ind], val);\n                arr[l] = max(arr[l], val);\n\t\t\t}\n\t\t\treturn;\n\t\t}\n        if(i<l or i>r){\n            return;\n        }\n        \n        if(l != r){\n            int m = (l+r)/2;\n            update(l, m, val, i, left(ind));\n            update(m+1, r, val, i, right(ind));\n\t\t\tpull(ind);\n        }\n    }\n\n    SegmentTree(int n) {\n        this->n = n;\n        arr = vector<T>(n, -INF);\n        st = vector<T>(4*n);\n\n        build(0, n-1, 0);\n    }\n    \n    void update(int index, T val) {\n        arr[index] = val;\n        update(0, n-1, val, index, 0);\n    }\n    \n    T query(int left, int right) {\n        return query(0, n-1, left, right, 0);\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<vector<int>> arr;\n        vector<int> points;\n        \n        for(int i=0; i<nums1.size(); i++) {\n            arr.push_back({nums1[i], nums2[i], nums1[i]+nums2[i]});\n            points.push_back(nums2[i]);\n        }\n        \n        sort(arr.begin(), arr.end(), [](vector<int>& a, vector<int>& b) {\n            if(a[0] == b[0]) return a[2] > b[2];\n            return a[0] < b[0];\n        });\n        \n        for(int i=0; i<queries.size(); i++) {\n            queries[i].push_back(i);\n            points.push_back(queries[i][1]);\n        }\n        \n        sort(points.begin(), points.end());\n        points.erase(unique(points.begin(), points.end()), points.end());\n        map<int,int> coord;\n        \n        for(int i=0; i<points.size(); i++) {\n            coord[points[i]] = i;\n        }\n        \n        sort(queries.rbegin(), queries.rend());\n        \n        vector<int> result(queries.size());\n        int i = arr.size()-1;\n        \n        using ll = long long;        \n        SegmentTree<ll> segTree(points.size());\n        \n        for(vector<int>& q : queries) {\n            while(i>=0 and arr[i][0] >= q[0]) {\n                segTree.update(coord[arr[i][1]], arr[i][2]);\n                i--;\n            }\n            \n            ll val = segTree.query(coord[q[1]], points.size());\n            \n            if(val == -INF) result[q[2]] = -1;\n            else result[q[2]] = val;\n        }\n        \n        return result;\n    }\n};\n```
['C++']