3-Line C++ Easy Solution without Loops
Intuition\nTo maximize efficiency, we can sort the items by price and compute the maximum beauty at each price threshold. By precomputing these values, we can a
# Intuition\nTo maximize efficiency, we can sort the items by price and compute the maximum beauty at each price threshold. By precomputing these values, we can answer each query in logarithmic time by finding the highest price that doesn\'t exceed the query price.\n\n# Approach\n1. **Sort Items**: Add a dummy item `{0, 0}` and sort items by price.\n2. **Compute Cumulative Maximum Beauty**: Use `partial_sum` to ensure each item at price `p` has the maximum beauty for prices up to `p`.\n3. **Answer Queries with Binary Search**: For each query, find the largest price less than or equal to the query using `upper_bound` and retrieve the corresponding maximum beauty.\n\n# Complexity\n- **Time complexity**: O((n + m) log n), where n is the number of items and m is the number of queries.\n- **Space complexity**: O(n + m), for storing sorted items and query results.\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>> v, vector<int> q) {\n        v.push_back({0, 0});     sort(begin(v), end(v));\n        partial_sum(begin(v), end(v), begin(v), [](auto p, auto& c) { c[1] = max(p[1], c[1]); return c; });\n        transform(begin(q), end(q), begin(q), [&](int i) { return v[upper_bound(begin(v), end(v), vector{i, INT_MAX}) - begin(v) - 1][1]; });\n        return q;\n    }\n};\n\n```\n\n![image.png](https://assets.leetcode.com/users/images/36076a17-a8aa-4b62-b514-44d7dc3778ba_1731373947.7271314.png)\n\n\n
['Sorting', 'C++']