Замовлення Айсберг#7569

Замовлення Айсберг

1 секунда

128 мегабайтів

Складна

Ви працюєте на біржі Метагонія. Нещодавно торговці в Метагонії дізналися про заявки айсберга, що використовуються на Лондонській фондовій біржі, і попросили вашого роботодавця додати таку функціональність. Фондова біржа — це фінансовий інститут, який отримує замовлення і генерує угоди.

Заявка айсберга — це п'ятірка цілих чисел $(I D, T, P, V, T V)$ (ID, T, P, V, TV). Кожна заявка має унікальний ідентифікатор $I D$ , тип $T$ (або $B U Y = 1$ BUY = 1, або $S E LL = 2$ SELL = 2), ціну $P$ , загальний залишковий обсяг $V$ і видимий обсяг $T V$ . Для кожної заявки також відстежується її поточний обсяг $C V$ і пріоритет $P R$ . Існує також глобальний лічильник пріоритетів обміну $GP$ . Заявка додається до набору заявок біржі.

Торги, що генеруються на біржі, представляють собою чотири цілі числа $(B U Y - I D, S E LL - I D, P, V)$ (BUY\text{-}ID, SELL\text{-}ID, P, V). Кожна угода містить $B U Y - I D$ BUY\text{-}ID і $S E LL - I D$ SELL\text{-}ID — ідентифікатори відповідних BUY і SELL замовлень, торгову ціну $P$ і обсяг торгів $V$ .

Коли заявка виставляється на торги, вона зіставляється із заявками, що вже є в реєстрі. Це відбувається наступним чином. Нехай отримано замовлення $a$ , у якого $T_{a} = S E LL$ T_a = SELL. Серед усіх заявок, виставлених на торги, ми шукаємо заявку $b$ , таку що $T_{b} = B U Y$ T_b = BUY і $P_{b} \geq P_{a}$ P_b \geq P_a. Ми вибираємо таку заявку $b$ , яка має найбільшу ціну, а якщо таких кілька — то з найменшим пріоритетом. Якщо така заявка $b$ існує, то $a$ генерує торгову угоду $t$ , у якої $B U Y - I D_{t} = I D_{b}$ BUY\text{-}ID_t = ID_b і $S E LL - I D_{t} = I D_{a}$ SELL\text{-}ID_t = ID_a за ціною $P_{t} = P_{b}$ P_t = P_b обсягом $V_{t} = min (V_{a}, C V_{b})$ V_t = \min(V_a,\,CV_b). Значення $V_{a}$ V_a, $V_{b}$ V_b і $C V_{b}$ CV_b зменшуються на обсяг угоди. Якщо після цього $V_{b} = 0$ V_b = 0, то заявка $b$ видаляється з реєстру заявок. Якщо $C V_{b} = 0$ CV_b = 0 (але $V_{b} > 0$ V_b > 0), то встановлюємо поточний обсяг заявки $b$ рівним $C V_{b} = min (V_{b}, T V_{b})$ CV_b = \min(V_b,\,TV_b), встановлюємо $P R_{b} = GP$ PR_b = GP, і збільшуємо $GP$ . Продовжуємо операції вибору $b$ і генерування торгів, поки не стане або $V_{a} = 0$ V_a = 0, або не залишиться таких заявок $b$ в реєстрі, що задовольняють умові можливості торгів. У цьому випадку ми додаємо замовлення $a$ до книги замовлень з $C V_{a} = min (V_{a}, T V_{a})$ CV_a = \min(V_a,\,TV_a) і $P R_{a} = GP$ PR_a = GP, а потім збільшуємо $GP$ . Коли процес зіставлення замовлення $a$ завершено з кількома угодами між однією парою замовлень $a$ і $b$ (і їх може бути багато!), вони всі об'єднуються в одну угоду з обсягом, рівним сумі обсягів окремих угод.

Якщо $T_{a} = B U Y$ T_a = BUY, ми шукаємо замовлення $b$ з $T_{b} = S E LL$ T_b = SELL і $P_{b} \leq P_{a}$ P_b \leq P_a і вибираємо таке замовлення $b$ з найменшою ціною і найменшим пріоритетом серед них. Решта процесу зіставлення описана вище, з угодами, що мають $B U Y - I D_{t} = I D_{a}$ BUY\text{-}ID_t = ID_a, $S E LL - I D_{t} = I D_{b}$ SELL\text{-}ID_t = ID_b, $P_{t} = P_{b}$ P_t = P_b, і $V_{t} = min (V_{a}, C V_{b})$ V_t = \min(V_a,\,CV_b).

Спочатку книга замовлень порожня. Вам надано кілька замовлень, які надходять на біржу одне за одним. Вам потрібно надрукувати згенеровані угоди і стан книги замовлень після обробки всіх замовлень.

Підказка: Пріоритет і $GP$ введені в умові задачі лише для формального опису алгоритму. Реальна реалізація не повинна відстежувати пріоритет. Зазвичай біржа просто веде список замовлень кожного типу за кожною ціною в своїй книзі замовлень, упорядкований за пріоритетом.

Вхідні дані

Перший рядок містить кількість заявок $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000). Кожен з наступних $n$ рядків представляє заявку. Кожна заявка задається п'ятіркою $I D T P V T V$ ID\,T\,P\,V\,TV, де $1 \leq I D \leq 1000000$ 1 \leq ID \leq 1000000, $T = 1$ T = 1 для BUY і $T = 2$ T = 2 для SELL, $1 \leq P \leq 100000$ 1 \leq P \leq 100000 і $1 \leq T V \leq V \leq 1 0^{9}$ 1 \leq TV \leq V \leq 10^9.

Вихідні дані

Для кожного замовлення надрукуйте всі угоди, згенеровані обробкою цього замовлення, у порядку зростання пар $(B U Y - I D, S E LL - I D)$ (BUY\text{-}ID, SELL\text{-}ID), кожну угоду на окремому рядку. Кожна угода повинна бути надрукована як пробілом розділена четвірка цілих чисел $B U Y - I D S E LL - I D P V$ BUY\text{-}ID\,SELL\text{-}ID\,P\,V. Гарантовано, що загальна кількість угод не перевищить $100000$ . Надрукуйте порожній рядок після всіх угод, за яким слідує книга замовлень. Кожне замовлення, яке все ще є в книзі, повинно бути надруковано як пробілом розділена шістка $I D T P V T V C V$ ID\,T\,P\,V\,TV\,CV, відсортована спочатку за $P$ , а потім за $P R$ .

Приклади

Приклад 1

Примітка

У прикладі перші чотири заявки мають $T = B U Y$ T = BUY. Припускаючи, що на початку торгів $GP$ дорівнює $1$ , після отримання цих заявок реєстр виглядає наступним чином, упорядкований за правилами відповідності з умови задачі для $T_{b} = B U Y$ T_b = BUY (спочатку за спаданням ціни, потім за зростанням пріоритету):

П'ята заявка ( $I D_{a} = 4321$ ID_a = 4321) має $T_{a} = S E LL$ T_a = SELL, $P_{a} = 99$ P_a = 99 і $V_{a} = 125$ V_a = 125 і може бути зіставлена з усіма чотирма заявками, наведеними в таблиці вище. Спочатку вона зіставляється двічі із заявкою $1111$ з найвищою ціною $101$ на загальний обсяг угоди $30$ , видаляє її з книги замовлень, збільшує $GP$ до $6$ в процесі, і зменшує $V_{a}$ V_a до $95$ . Потім є три інші заявки за ціною $100$ . Один прохід зіставлення через них генерує три угоди на загальний обсяг $85$ (обсяг $20$ із заявкою $42$ , обсяг $50$ із заявкою $239$ , видаляє її з книги, обсяг $15$ із заявкою $1234$ ), збільшує $GP$ до $8$ , і зменшує $V_{a}$ V_a до $10$ . Залишилися заявки в книзі показані нижче:

Останнє зіставлення із заявкою $42$ генерує угоду з обсягом $10$ (на загальний обсяг $30$ для зіставлень із заявкою $42$ ) і заявка $4321$ завершена ( $V_{a} = 0$ V_a = 0). Чотири відповідні загальні угоди для заявки $4321$ надруковані у вихідних даних прикладу. Залишилася книга замовлень:

Шоста заявка BUY (з $I D = 5678$ ID = 5678) додається до книги замовлень ( $GP$ стає $9$ ):

Остання, сьома заявка (з $I D = 8765$ ID = 8765), може бути зіставлена лише із заявкою $5678$ через цінову умову, генерує угоду з обсягом $30$ , заявка $5678$ видаляється з книги замовлень, тоді як заявка $8765$ додається. Тепер книга замовлень має як BUY, так і SELL заявки: