leetcode

Solution to some Leetcode problems written in C++

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

1801.cpp (1464B)

0 class Solution { 1 static const int mod = 1e9 + 7; 2 using tii_t = tuple<int, int>; 3 4 template <typename C, typename T, typename M> 5 void exchange(T &first, M &second, int price, int amount) const { 6 const auto cmp = C(); 7 while (!first.empty() && amount > 0) { 8 const auto [cprice, camount] = first.top(); 9 if (cmp(cprice, price)) break; 10 first.pop(); 11 12 if (camount <= amount) 13 amount -= camount; 14 else { 15 first.emplace(cprice, camount - amount); 16 amount = 0; 17 } 18 } 19 if (amount > 0) second.emplace(price, amount); 20 } 21 22 template <typename T> long long count(T &pq) const { 23 long long res = 0; 24 while (!pq.empty()) { 25 const auto [_, amount] = pq.top(); 26 res = (res + amount) % mod; 27 pq.pop(); 28 } 29 return res; 30 } 31 32 public: 33 int getNumberOfBacklogOrders(const vector<vector<int>> &orders) const { 34 priority_queue<tii_t, vector<tii_t>, greater<tii_t>> buy; 35 priority_queue<tii_t, vector<tii_t>, less<tii_t>> sell; 36 int res = 0; 37 38 for (const auto &order : orders) { 39 if (!order[2]) 40 exchange<greater<int>>(buy, sell, order[0], order[1]); 41 else 42 exchange<less<int>>(sell, buy, order[0], order[1]); 43 } 44 45 return (count(buy) + count(sell)) % mod; 46 } 47 };