leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2070.cpp (1834B)

0 1 // Ordered Query 2 class Solution { 3 public: 4 vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) { 5 static int maxi[100001] = {0}; 6 const int n = size(items); 7 8 sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; }); 9 10 vector<int> keys = {0}; 11 keys.reserve(n); 12 13 for (int i = 0, prev = -1; i < n; i++) { 14 if (items[i][0] != prev) { 15 keys.push_back(prev = items[i][0]); 16 maxi[size(keys)] = maxi[size(keys) - 1]; 17 } 18 maxi[size(keys)] = max(maxi[size(keys)], items[i][1]); 19 } 20 21 for (auto &query : queries) { 22 const auto it = upper_bound(begin(keys), end(keys), query); 23 const auto idx = distance(begin(keys), it); 24 query = maxi[idx]; 25 } 26 27 return queries; 28 } 29 }; 30 31 // Offline Query 32 class Solution { 33 public: 34 vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) const { 35 static int idxes[100001] = {0}; 36 const int n = size(items), m = size(queries); 37 38 iota(idxes, idxes + m, 0); 39 sort(idxes, idxes + m, [&](int a, int b) { return queries[a] < queries[b]; }); 40 sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; }); 41 42 int maxi = 0, idx = 0; 43 for (int i = 0, prev = -1; i < n; i++) { 44 const int price = items[i][0], value = items[i][1]; 45 46 if (price != prev) { 47 while (idx < m && queries[idxes[idx]] < price) 48 queries[idxes[idx++]] = maxi; 49 if (idx == m) break; 50 prev = price; 51 } 52 53 maxi = max(maxi, value); 54 } 55 while (idx < m) 56 queries[idxes[idx++]] = maxi; 57 58 return queries; 59 } 60 };