Description

Submission

class Solution {
    typedef pair<int, int> PII;
    const int M = 1e9 + 7;
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        // {price, amount}
        priority_queue<PII, vector<PII>> pqBuy;
        priority_queue<PII, vector<PII>, greater<>> pqSell;

        for(auto order: orders) {
            int price = order[0];
            int amount = order[1];
            int orderType = order[2];

            if(orderType == 0) { // buy
                while(amount > 0 && !pqSell.empty()) {
                    auto [sellPrice, sellAmount] = pqSell.top();
                    if(sellPrice <= price) {
                        pqSell.pop();
                        if(amount <= sellAmount) {
                            pqSell.emplace(sellPrice, sellAmount-amount);
                            amount = 0;
                        } else {
                            amount -= sellAmount;
                        }
                    } else {
                        break;
                    }
                }
                if(amount > 0) {
                    pqBuy.emplace(price, amount);
                }
            } else { // sell
                while(amount > 0 && !pqBuy.empty()) {
                    auto [buyPrice, buyAmount] = pqBuy.top();
                    if(buyPrice >= price) {
                        pqBuy.pop();
                        if(amount < buyAmount) {
                            pqBuy.emplace(buyPrice, buyAmount-amount);
                            amount = 0;
                        } else {
                            amount -= buyAmount;
                        }
                    } else {
                        break;
                    }
                }
                if(amount > 0) {
                    pqSell.emplace(price, amount);
                }
            }
        }

        int ret = 0;
        while(!pqBuy.empty()) {
            ret += pqBuy.top().second;
            ret %= M;
            pqBuy.pop();
        }

        while(!pqSell.empty()) {
            ret += pqSell.top().second;
            ret %= M;
            pqSell.pop();
        }

        return ret;
    }
};