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