[C++] Sorting + Map + Concept of Prefix Sum (Designing FloorKey in C++)
\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        map<int,int> m;\n        vector<int> ans
```\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        map<int,int> m;\n        vector<int> ans;\n        sort(items.begin(),items.end());\n        int maxBeauty = 0;\n        \n\t\t// I am filling the map in such a way that every element has the following parts - \n\t\t// First element of a map element (it->first) : Contains PRICE\n\t\t// Second element of a map element (it->second) : Contains Maximum BEAUTY till that PRICE (i.e till it->first)\n\t\t// In this way we are keeping prefix price-beauty map \n\t\t// Since it is a map, it is sorted in terms of the first element, i.e in terms of PRICE.\n        for(int i=0; i<items.size(); i++){\n            int currMaxPrice = items[i][0];\n            int currBeauty = items[i][1];\n            maxBeauty = max(maxBeauty,currBeauty);\n            m[currMaxPrice] = maxBeauty;\n        }\n        for(int i=0; i<queries.size(); i++){\n            int maxAllowedPrice = queries[i];\n            auto begin = m.begin();\n            auto end = --m.end();\n\t\t\t\n\t\t\t// If the current query PRICE is less that the smallest PRICE in the map, \n\t\t\t// then there are no PRICE which are less than query[i]\n            if(begin->first > maxAllowedPrice)\n                ans.push_back(0);\n\t\t\t\t\n\t\t\t// If the current query price is more than the maximum PRICE in the map \n\t\t\t// (i.e it is greater than the last element PRICE in the map), \n\t\t\t// then it is obviously greater than all other PRICE values in the map. \n\t\t\t// In this case we add the last elements BEAUTY, which is the cummulative maximum BEAUTY.\n            else if(end->first < maxAllowedPrice){\n                ans.push_back(end->second);\n            }\n            else{\n                auto find = m.find(maxAllowedPrice);\n\t\t\t\t\n\t\t\t\t// If the exact PRICE is there in the map, then that element will contain the maximum BEAUTY till that PRICE.\n\t\t\t\t// So we can simply add that BEAUTY\n                if(find != m.end())\n                    ans.push_back(find->second);\n\t\t\t\t\n\t\t\t\t// Else we find the lower_bound (please read about lower_bound, incase you don\'t know).\n\t\t\t\t// And we add the immediate previous BEAUTY value.\n                else{\n                    auto lower = m.lower_bound(maxAllowedPrice);\n                    --lower;\n                    ans.push_back(lower->second);\n                }\n            }\n            \n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'C', 'Sorting', 'Binary Tree', 'Prefix Sum', 'C++']