Simple map solution in C++
Intuition\nWe can sort the query and points by x values.\nAnd for each query, since x is decreasing, we just add more points to the candidate set.\nNow, we cons
# Intuition\nWe can sort the query and points by x values.\nAnd for each query, since x is decreasing, we just add more points to the candidate set.\nNow, we consider all qulified y values. We save a map that maps each y value to (x + y). \n\nSince we are querying the maximum values with y >= y\',\nthe larger the key is, the smaller the value should be. When we insert a (key, value) pair in the map, we should trim the map to keep the monotonicity in the map. Just like how we maintain a monotonic stack/queue.\n\n\n# Complexity\n- Time complexity:\nO((n + q)logn + qlogq)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    void update(map<int, int> &values, int key, int value) {\n        auto t = values.lower_bound(key);\n        if (t != values.end() /*&& t->second >= value*/) {\n            return;\n        }\n        if (t != values.begin()) {\n            --t;\n            while (t->second <= value) {\n                if (t == values.begin()) {\n                    values.erase(t);\n                    break;\n                } else {\n                    values.erase(t--);\n                }\n            }\n        }\n        values.insert({key, value});\n    }\n    \n    int query(const map<int, int> values, int key) {\n        const auto t = values.lower_bound(key);\n        return t == values.end() ? (-1) : t->second;\n    }\n    \npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        const int n = nums1.size();\n        vector<pair<int, int>> v(n);\n        for (int i = 0; i < n; ++i) {\n            v[i] = {nums1[i], nums2[i]};\n        }\n        sort(v.begin(), v.end());\n        const int m = queries.size();\n        vector<int> ind(m);\n        for (int i = 0; i < m; ++i) {\n            ind[i] = i;\n        }\n        sort(ind.begin(), ind.end(), [&](const int x, const int y) {\n            return queries[x][0] > queries[y][0];\n        });\n        vector<int> r(m);\n        map<int, int> values;\n        for (int i = 0, j = n - 1; i < m; ++i) {\n            for (; j >= 0 && v[j].first >= queries[ind[i]][0]; update(values, v[j].second, v[j].first + v[j].second), --j)\n            ;\n            r[ind[i]] = query(values, queries[ind[i]][1]);\n        }\n        return r;\n    }\n};\n```
['C++']