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
/* 2019-12-13 Jędrzej Pacanowski
 * SIS, PA2019 */
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

typedef unsigned long long u64;
typedef unsigned int u32;
std::vector<u64> staw; // liczby: [1 ; 10**12]

// <https://stackoverflow.com/questions/15843525/how-do-you-insert-the-value-in-a-sorted-vector>
template<typename T> void insert_sorted( std::vector<T>& vec, T const& item){
	vec.insert(   std::upper_bound( vec.begin(), vec.end(), item ),  item );
}

static inline void dodaj_szprotka(u64 waga)
{ insert_sorted(staw, waga); }

static inline void usun_szprotka(u64 waga)
{	auto it = std::lower_bound(staw.begin(),staw.end(),waga);
	staw.erase(it, it+1);
}

void uwaga_szczupak(u64 waga_sz, u64 cel)
{
	if(cel <= waga_sz){std::cout<<"0\n";return;}
	
	u32 licznik = 0;
	std::vector<bool> edible(staw.size(),true);
	
	while(waga_sz < cel){
		auto najw = std::upper_bound(staw.begin(), staw.end(), waga_sz);
		if(najw == staw.begin()){ // nie moze wiecej zjesc
			std::cout<< "-1\n";
			return;
		}
		u32 najw_idx = std::distance(staw.begin(), najw);
		for(u32 i=najw_idx-1;; --i){
			if(edible[i] && staw[i] < waga_sz){
				licznik++;
				waga_sz += staw[i];
				edible[i] = false;
				break;
			}
			
			if(i==0){std::cout<< "-1\n"; return;}
		}
	}
	
	std::cout<< licznik <<'\n';
}

int main()
{
	std::cin.tie(0);std::ios_base::sync_with_stdio(false);
	unsigned int N; // [1; 300 k]
	std::cin>> N;
	
	staw.reserve(N);
	for(unsigned int i=0; i<N; i++){
		u64 _temp;
		std::cin>> _temp;
		staw.push_back(_temp);
	}
	
	std::sort(staw.begin(), staw.end());
	
	unsigned int Q; // [1; 100 k]
	std::cin>> Q;
	for(unsigned int q=0; q<Q; q++){
		unsigned short event;
		u64 _waga, _cel_szczupaka;
		std::cin>> event >> _waga; // wczytaj 2 liczby
		
		if(event == 1){
			std::cin>> _cel_szczupaka;
			uwaga_szczupak(_waga, _cel_szczupaka);
		}else if(event == 2) dodaj_szprotka(_waga);
		else if(event == 3) usun_szprotka(_waga);
		else std::cerr<< "???\n";
	}
	
	return 0;
}