#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;

enum class Side {
    BID = 0,
    ASK = 1,
};

struct Order {
    int Price;
    int Amount;
    int OrderID;
    Side side;
};

struct Deal {
    int Price;
    int Amount;
    int OrderID_ASK;
    int OrderID_BID;
};

class OrderBook {
private:
    using Price = int;
    using Time = int;
    using Id = int;
    using Amount = int;

    struct Comp_bid {
        bool operator () (const tuple<Price, Time, Id> &a, const tuple<Price, Time, Id> &b) const {
            if(get<0>(a) == get<0>(b)) {
                if(get<1>(a) == get<1>(b)) {
                    return get<2>(a) < get<2>(b);
                }
                return get<1>(a) < get<1>(b);
            }
            return get<0>(a) > get<0>(b);
        }
    };

    set<tuple<Price, Time, Id>, Comp_bid> bid_s;
    set<tuple<Price, Time, Id>> ask_s;
    unordered_map<Id, tuple<Price, Time, Amount, Side>> id_to_info;

    Time tm_ = 0;
    Time get_time() {
        return tm_++;
    }

    bool price_comp(Side side, Price a, Price b) {
        if(side == Side::ASK) {
            return a >= b;
        }
        else {
            return a <= b;
        }
    }

    template <typename T>
    vector<Deal> add_order_(const Order& order, T& orders) {
        vector<Deal> deals;
        Amount order_amount = order.Amount;
        Price pr = order.Price;
        Time tm = get_time();
        Id order_id = order.OrderID;
        Side order_side = order.side;
        while(!orders.empty() && order_amount > 0 && price_comp(order_side, get<0>(*orders.begin()), pr)) {
            auto pot_order_it = orders.begin();
            Id pot_order_id = get<2>(*pot_order_it);
            auto& pot_order_info = id_to_info[pot_order_id];
            Amount new_amount = get<2>(pot_order_info) - order_amount;
            if(new_amount > 0) {
                id_to_info[pot_order_id] = {get<0>(pot_order_info), get<1>(pot_order_info), new_amount, get<3>(pot_order_info)};
            }
            else {
                orders.erase(orders.begin());
                id_to_info.erase(pot_order_id);
            }
            Deal deal;
            deal.Amount = min(order_amount, get<2>(pot_order_info));
            deal.Price = get<1>(pot_order_info);
            if(order.side == Side::ASK) {
                deal.OrderID_ASK = order_id;
                deal.OrderID_BID = pot_order_id;
            }
            else {
                deal.OrderID_ASK = pot_order_id;
                deal.OrderID_BID = order_id;
            }
            deals.push_back(deal);
            order_amount = max(0, - new_amount);
        }
        if(order_amount > 0) {
            if(order.side == Side::ASK) {
                ask_s.insert({pr, tm, order_id});
            }
            else {
                bid_s.insert({pr, tm, order_id});
            }
            id_to_info[order_id] = {pr, tm, order_amount, order_side};
        }
        return deals;
    }

public:
    vector<Deal> add_order(const Order& order) {
        if(order.side == Side::ASK) {
            return add_order_(order, bid_s);
        }
        else {
            return add_order_(order, ask_s);
        }
    }

    Amount delete_order(Id order_id) {
        auto& order_info = id_to_info[order_id];
        Side sd = get<3>(order_info);
        Price pr = get<0>(order_info);
        Time tm = get<1>(order_info);
        Amount amnt = get<2>(order_info);
        if(sd == Side::ASK) {
            ask_s.erase({pr, tm, order_id});
        }
        else {
            bid_s.erase({pr, tm, order_id});
        }
        id_to_info.erase(order_id);
        return amnt;
    }
};



int main() {
    OrderBook book;
    book.add_order({10, 5, 1, Side::ASK});
    book.add_order({5, 2, 2, Side::ASK});
    book.add_order({11, 4, 3, Side::BID});

    book.add_order({8, 1, 4, Side::BID});
    book.add_order({8, 1, 4, Side::ASK});
    book.delete_order(1);
    return 0;
}