Tehtäväsi on toteuttaa tietorakenne, joka pitää yllä kokoelmaa luvuista. Tietorakenteeseen pystyy lisäämään tehokkaasti $k$ kappaletta lukua $x$ sekä poistamaan $k$ pienintä lukua ja laskemaan niiden summan.

Voit olettaa, että jokaisessa operaatiossa $k$ ja $x$ ovat enintään $10^9$.

Python

Toteuta tiedostoon quickadd.py luokka QuickAdd, jossa on seuraavat funktiot:

• add: lisää $k$ kappaletta lukua $x$ tietorakenteeseen
• remove: poista $k$ pienintä lukua ja palauta näiden lukujen summa

Kummankin funktion tulee toimia tehokkaasti.

class QuickAdd:
    def add(self, k, x):
        # TODO

    def remove(self, k):
        # TODO

if __name__ == "__main__":
    q = QuickAdd()
    q.add(5,3)
    print(q.remove(2)) # 6
    q.add(8,1)
    print(q.remove(4)) # 4
    print(q.remove(7)) # 13
    q.add(10**9,123)
    print(q.remove(10**9)) # 123000000000

Java

Toteuta tiedostoon QuickAdd.java luokka QuickAdd, jossa on seuraavat metodit:

• add: lisää $k$ kappaletta lukua $x$ tietorakenteeseen
• remove: poista $k$ pienintä lukua ja palauta näiden lukujen summa

Kummankin metodin tulee toimia tehokkaasti.

public class QuickAdd {
    public void add(int k, int x) {
        // TODO
    }

    public long remove(int k) {
        // TODO
    }

    public static void main(String[] args) {
        QuickAdd q = new QuickAdd();
        q.add(5,3);
        System.out.println(q.remove(2)); // 6
        q.add(8,1);
        System.out.println(q.remove(4)); // 4
        System.out.println(q.remove(7)); // 13
        q.add(1000000000,123);
        System.out.println(q.remove(1000000000)); // 123000000000
    }
}