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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h> 

using namespace std; 

typedef long long LL;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	map<LL, int> map;
	map.clear();
	int n;
	cin >> n;
	LL sum = 0;
	for (int i = 0; i < n; i++) {
		LL val;
		cin >> val;
		map[val]++;
		sum += val;
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int a;
		cin >> a;
		if (a == 1) {
			LL weight, c;
			cin >> weight >> c;
			LL goal = c - weight;
			//cout << "SUMA: " << goal << " " << sum << endl;
			if (goal > sum) {
				cout << -1 << '\n';
				continue;
			}

			vector <pair<LL, int>> vec;
			int zlicz = 0;
			bool succ = 1;

			int j = 0;
			while (1) {
				if (goal <= 0)
					break;
				auto it = map.lower_bound(weight);
				//cout << "ZNALEZIONE" << it->first << "  "<< it->second << endl;
				//cout << "WAGA" << weight << endl;
				if (it == map.begin() && it->first >= weight) {
					//cout << "dupa";
					succ = 0;
					break;
				}
				if ((it != map.begin() && it->first >= weight) || it == map.end())
					--it;
				//cout << "ZJADANIE " << it->first << " " << it->second << endl;
				auto fsize = it->first;
				auto fcount = it->second;
				vec.push_back(make_pair(fsize, fcount));
				zlicz++;
				weight += fsize;
				goal -= fsize;
				//cout << fsize << endl;
				//cout << map[fsize] << endl;
				if (fcount > 1)
					map[fsize]--;
				else
					map.erase(fsize);
				//cout << map[fsize] << endl;
			}

			if (succ)
				cout << zlicz << '\n';
			else
				cout << -1 << '\n';

			for (int i = vec.size() -1; i>= 0; i--)
				map[vec[i].first] = vec[i].second;

		}
		else if(a == 2) {
			LL b;
			cin >> b;
			sum += b;
			map[b]++;
		}
		else {
			LL b;
			cin >> b;
			sum -= b;
			if (map[b] > 1)
				map[b]--;
			else
				map.erase(b);
		}
	}
	return 0; 
}