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