Sort + binary search||23ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nSort the items w.r.t. default ordering.\nConstruct the array mostBeauty for which mostB
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSort the `items` w.r.t. default ordering.\nConstruct the array `mostBeauty` for which `mostBeauty[i]` is the max beauty up to index `i` for the sorted `items`. Do binary search for each query in `queries`\n\n1st C++ is slow.\n2nd C++ uses bit manipulation to pack vector to an uint64 which becomes a fast code.\n3rd C++ uses C++ STL sort, partial_sum with lambda, for_each with lamda & upper_bound which is the fastest one & a good exercise for using STL\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. sort `items` w.r.t. default ordering.\n2. Construct the array `mostBeauty` for which `mostBeauty[i] = max(mostBeauty[i-1], items[i][1])`\n3. Transverse the loop, for each query in queries as follows\n```\nint query = queries[i];\nvector<int>&& target={query, INT_MAX};\n// Use upper_bound to find the first item with a price > query\nint j = upper_bound(items.begin(), items.end(), target)-items.begin();\n\n// If j is 0, no items have price <= query\nif (j == 0) ans[i] = 0;\nelse ans[i] = mostBeauty[j - 1];\n```\n4. 2nd C++ uses bit manipulation to pack vector to an uint64;`priceIdx[i]=((unsigned long long)items[i][0]<<32)+i;`\n5. The binary search part is as follws\n```\nunsigned long long target=((unsigned long long)query<<32)+UINT_MAX;\n// Use upper_bound to find the first item with a price > query\nint j = upper_bound(priceIdx.begin(), priceIdx.end(), target)-priceIdx.begin();\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O((n+m)\\log n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code slow 76ms\n```cpp []\nclass Solution {\npublic:\n    static vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        sort(items.begin(), items.end()); // Sort items by price\n        const int n = items.size(), m = queries.size();\n\n        vector<int> mostBeauty(n);\n        mostBeauty[0] = items[0][1];\n\n        // Build up the mostBeauty array\n        for (int i = 1; i < n; i++)\n            mostBeauty[i] = max(mostBeauty[i-1], items[i][1]);\n\n        vector<int> ans(m);\n        for (int i = 0; i < m; i++) {\n            int query = queries[i];\n            vector<int>&& target={query, INT_MAX};\n            // Use upper_bound to find the first item with a price > query\n            int j = upper_bound(items.begin(), items.end(), target)-items.begin();\n            // If j is 0, no items have price <= query\n            if (j == 0) ans[i] = 0;\n            else ans[i] = mostBeauty[j - 1];\n        }\n\n        return ans;\n    }\n};\n\n```\n# C++ ||23ms Beats 100%\n```\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        const int n = items.size(), m = queries.size();\n        vector<unsigned long long> priceIdx(n);\n        for(int i=0; i<n; i++)\n            priceIdx[i]=((unsigned long long)items[i][0]<<32)+i;\n        sort(priceIdx.begin(), priceIdx.end());\n\n        vector<int> mostBeauty(n);\n        mostBeauty[0] = items[priceIdx[0]&UINT_MAX][1];\n        // Build up the mostBeauty array\n        for (int i = 1; i < n; i++)\n            mostBeauty[i] = max(mostBeauty[i-1], items[priceIdx[i]&UINT_MAX][1]);\n\n        vector<int> ans(m);\n        for (int i = 0; i < m; i++) {\n            int query = queries[i];\n            unsigned long long target=((unsigned long long)query<<32)+UINT_MAX;\n            // Use upper_bound to find the first item with a price > query\n            int j = upper_bound(priceIdx.begin(), priceIdx.end(), target)-priceIdx.begin();\n            // If j is 0, no items have price <= query\n            if (j == 0) ans[i] = 0;\n            else ans[i] = mostBeauty[j-1];\n        }\n        return ans;\n    }\n};\n\n \nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# 3rd C++ STL solution||21ms beats 100%\n```\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        const int n = items.size(), m = queries.size();\n        vector<unsigned long long> PB(n);\n        for(int i=0; i<n; i++)\n            PB[i]=((unsigned long long)items[i][0]<<32)+items[i][1];\n        sort(PB.begin(), PB.end());\n\n        vector<int> mostBeauty(n);\n        partial_sum(PB.begin(), PB.end(), mostBeauty.begin(), [&](int sum, auto x){\n            return sum=max(sum, (int)(x&INT_MAX));\n        });\n\n        vector<int> ans(m);\n        for_each(queries.begin(), queries.end(), [&, i=0](int query) mutable{\n             unsigned long long target=((unsigned long long)query<<32)+UINT_MAX;\n            // Use upper_bound to find the first item with a price > query\n            int j = upper_bound(PB.begin(), PB.end(), target)-PB.begin();\n            // If j is 0, no items have price <= query\n            ans[i++]= (j == 0) ?0: mostBeauty[j-1];\n        });\n        return ans;\n    }\n};\n\n \nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}()\n```
['Array', 'Binary Search', 'Bit Manipulation', 'Sorting', 'C++']