leetcode

commit 3b519d6d4e2182308fb49b25f925dfd1311e7dcf
parent 8c8e75e017cc93875a54dd9270117bd82a08d66b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 30 Jun 2024 21:23:50 +0200

1 Random Problem

Diffstat:
A
Problems/1801.cpp
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 49 insertions(+), 0 deletions(-)
diff --git a/Problems/1801.cpp b/Problems/1801.cpp
@@ -0,0 +1,48 @@
+class Solution {
+    static const int mod = 1e9 + 7;
+    using tii_t = tuple<int, int>;
+
+    template <typename C, typename T, typename M>
+    void exchange(T &first, M &second, int price, int amount) const {
+        const auto cmp = C();
+        while (!first.empty() && amount > 0) {
+            const auto [cprice, camount] = first.top();
+            if (cmp(cprice, price)) break;
+            first.pop();
+
+            if (camount <= amount)
+                amount -= camount;
+            else {
+                first.emplace(cprice, camount - amount);
+                amount = 0;
+            }
+        }
+        if (amount > 0) second.emplace(price, amount);
+    }
+
+    template <typename T> long long count(T &pq) const {
+        long long res = 0;
+        while (!pq.empty()) {
+            const auto [_, amount] = pq.top();
+            res = (res + amount) % mod;
+            pq.pop();
+        }
+        return res;
+    }
+
+  public:
+    int getNumberOfBacklogOrders(const vector<vector<int>> &orders) const {
+        priority_queue<tii_t, vector<tii_t>, greater<tii_t>> buy;
+        priority_queue<tii_t, vector<tii_t>, less<tii_t>> sell;
+        int res = 0;
+
+        for (const auto &order : orders) {
+            if (!order[2])
+                exchange<greater<int>>(buy, sell, order[0], order[1]);
+            else
+                exchange<less<int>>(sell, buy, order[0], order[1]);
+        }
+
+        return (count(buy) + count(sell)) % mod;
+    }
+};
diff --git a/README.md b/README.md
@@ -975,6 +975,7 @@ for solving problems.
 |  1797  |   Medium   | [Design Authentication Manager](Problems/1797.cpp)                                                 |
 |  1798  |   Medium   | [Maximum Number of Consecutive Values You Can Make](Problems/1798.cpp)                             |
 |  1799  |   Medium   | [Maximize Score After N Operations](Problems/1799.cpp)                                             |
+|  1801  |   Medium   | [Number of Orders in the Backlog](Problems/1801.cpp)                                               |
 |  1802  |   Medium   | [Maximum Value at a Given Index in a Bounded Array](Problems/1802.cpp)                             |
 |  1806  |   Medium   | [Minimum Number of Operations to Reinitialize a Permutation](Problems/1806.cpp)                    |
 |  1807  |   Medium   | [Evaluate the Bracket Pairs of a String](Problems/1807.cpp)                                        |