leetcode

commit f33f4fe8a7e639cc3ca7fe05fc09a206f3f26ee6
parent 9a6749b89acb537e021dd3c84cb65f140bcda56c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 18 Jul 2024 22:56:43 +0200

1 Random Problem

Diffstat:
A
Problems/2070.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 62 insertions(+), 0 deletions(-)
diff --git a/Problems/2070.cpp b/Problems/2070.cpp
@@ -0,0 +1,61 @@
+
+// Ordered Query
+class Solution {
+  public:
+    vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) {
+        static int maxi[100001] = {0};
+        const int n = size(items);
+
+        sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; });
+
+        vector<int> keys = {0};
+        keys.reserve(n);
+
+        for (int i = 0, prev = -1; i < n; i++) {
+            if (items[i][0] != prev) {
+                keys.push_back(prev = items[i][0]);
+                maxi[size(keys)] = maxi[size(keys) - 1];
+            }
+            maxi[size(keys)] = max(maxi[size(keys)], items[i][1]);
+        }
+
+        for (auto &query : queries) {
+            const auto it = upper_bound(begin(keys), end(keys), query);
+            const auto idx = distance(begin(keys), it);
+            query = maxi[idx];
+        }
+
+        return queries;
+    }
+};
+
+// Offline Query
+class Solution {
+  public:
+    vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) const {
+        static int idxes[100001] = {0};
+        const int n = size(items), m = size(queries);
+
+        iota(idxes, idxes + m, 0);
+        sort(idxes, idxes + m, [&](int a, int b) { return queries[a] < queries[b]; });
+        sort(begin(items), end(items), [](auto &a, auto &b) { return a[0] < b[0]; });
+
+        int maxi = 0, idx = 0;
+        for (int i = 0, prev = -1; i < n; i++) {
+            const int price = items[i][0], value = items[i][1];
+
+            if (price != prev) {
+                while (idx < m && queries[idxes[idx]] < price)
+                    queries[idxes[idx++]] = maxi;
+                if (idx == m) break;
+                prev = price;
+            }
+
+            maxi = max(maxi, value);
+        }
+        while (idx < m)
+            queries[idxes[idx++]] = maxi;
+
+        return queries;
+    }
+};
diff --git a/README.md b/README.md
@@ -1053,6 +1053,7 @@ for solving problems.
 |  2058  |   Medium   | [Find the Minimum and Maximum Number of Nodes Between Critical Points](Problems/2058.cpp)          |
 |  2063  |   Medium   | [Vowels of All Substrings](Problems/2063.cpp)                                                      |
 |  2064  |   Medium   | [Minimized Maximum of Products Distributed to Any Store](Problems/2064.cpp)                        |
+|  2070  |   Medium   | [Most Beautiful Item for Each Query](Problems/2070.cpp)                                            |
 |  2073  |    Easy    | [Time Needed to Buy Tickets](Problems/2073.cpp)                                                    |
 |  2074  |   Medium   | [Reverse Nodes in Even Length Groups](Problems/2074.cpp)                                           |
 |  2079  |   Medium   | [Watering Plants](Problems/2079.cpp)                                                               |