1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

int n, q, A;
long long B, C;
int i;
int wynik;
multiset<long long>Rybki;
multiset<long long>::iterator it=Rybki.begin();

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // Dodaje n szprotek do multizbioru
    cin>>n;
    for (i=0; i<n; ++i){
        long long A;
        cin>>A;
        Rybki.insert(A);
    }

    //Dodajemy pusty staw
    Rybki.insert(0);

    // Wczytuje q zapytan
    // O(?)
    cin>>q;
    while(q>0){
        wynik=0;
        cin>>A;
        // Nic nie robi
        // Ma sprawdzac ile szprotek musi zjesc szczupak aby osiagnac swoja wage
        // Ma sprawdzac czy jest to mozliwe czy jest to mozliwe
        // O(?)
        if (A==1){
            vector<long long>Zjedzone;
            cin>>B>>C;
            /*for (it=Rybki.begin(); it!=Rybki.end(); ++it)
                cout<<*it<<" ";
            cout<<"\n";*/
            while(B<C){
                it=Rybki.lower_bound(B);
                --it;
                if(*it==0){
                    wynik=-1;
                    break;
                }
                else{
                    Zjedzone.push_back(*it);
                    B+=*it;
                    Rybki.erase(Rybki.lower_bound(*it));
                    ++wynik;
                }
            }
            for (i=0; i<Zjedzone.size(); ++i)
                Rybki.insert(Zjedzone[i]);
            cout<<wynik<<"\n";
        }
        // Poprawnie dodaje po jednej szprotce na zapytanie
        // O(log(k)), k=Rybki.size()
        else if (A==2){
            cin>>B;
            Rybki.insert(B);
        }
        // Poprawnie odejmuje po jednej szprotce na zapytanie
        // O(log^2(k)), k=Rybki.size()
        else{
            cin>>B;
            Rybki.erase(Rybki.lower_bound(B));
        }/*
        for (it=Rybki.begin(); it!=Rybki.end(); ++it)
            cout<<*it<<" ";
        cout<<"\n";*/
        --q;
    }


    return 0;
}