Fișierul intrare/ieșire | magazin.in, magazin.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Magazin (clasele 8-9)
Un magazin de antichități cumpără și vinde obiecte. Proprietarul vânează mereu chilipiruri și adaugă obiecte în stoc. Pentru vânzare, magazinul folosește un site web care listează numai cele mai ieftine K obiecte, în ordinea crescătoare a prețului. Dacă magazinul are mai puțin de K obiecte în stoc, site-ul le arată pe toate. Uneori un client vizitează site-ul și cumpără un obiect. Și la adăugarea în stoc, și la vânzare, site-ul se actualizează automat cu cele mai ieftine K obiecte disponibile.
Magazinul pornește cu stocul gol. Dându-se o listă de N operații de adăugare și vânzare, ajutați-l pe proprietar să-și calculeze veniturile.
Date de intrare
Fișierul de intrare magazin.in va conține pe prima linie două numere N K, separate printr-un spațiu. N este numărul de operații, iar K este numărul de obiecte vizibile pe site. Urmează N linii într-una din formele:
- 1 x — proprietarul adaugă în stoc un obiect de valoare x (număr natural pozitiv).
- 2 q — pe site se vinde al q-lea cel mai ieftin obiect.
Date de ieșire
În fișierul de ieșire magazin.out se va tipări, pentru fiecare operație de vânzare, suma încasată de magazin.
Restricții
- 1 ≤ N ≤ 300.000
- 1 ≤ K ≤ 100
- 1 ≤ x ≤ 1.000.000.000 pentru toate obiectele adăugate
- 1 ≤ q ≤ K pentru toate obiectele vândute
- Se garantează că există q obiecte în stoc la momentul vânzării.
Exemplu
magazin.in | magazin.out | Explicație |
---|---|---|
10 3 1 5 1 8 1 3 2 2 1 10 1 4 1 12 2 2 1 15 2 3 |
5 4 10 |
Magazinul deține obiectele 5, 8, 3. Al doilea ca preț este 5. Magazinul deține obiectele 8, 3, 10, 4, 12. Al doilea ca preț este 4. Magazinul deține obiectele 8, 3, 10, 12, 15. Al treilea ca preț este 10. |