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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128 | #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
const int INF = 1000000009;
const LL LINF = 1000000000000000009LL;
#define FOR(i, b, e) for (int i = b; i <= e; ++i)
#define FORD(i, b, e) for (int i = b; i >= e; --i)
#define REP(i, n) FOR (i, 0, n - 1)
#define REV(i, n) FORD (i, n - 1, 0)
#define PB push_back
#define PP pop_back
#define MP make_pair
#define MT make_tuple
#define ST first
#define ND second
#define SZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define UNIQ(c) (c).erase(unique(ALL(c)), (c).end());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/hash_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; /*find_by_order() order_of_key()*/
template <typename T, typename S>
ostream &operator<<(ostream &out, const pair<T, S> &v)
{
return (out << "(" << v.ST << ", " << v.ND << ")");
}
#define DEBUG(s) s
#ifdef local_comp
#define PRINT(V) cout << "#" << #V << ": " << V << endl;
#else
#define PRINT(v)
#endif
const int N = 500005;
multiset<LL> vals;
LL tab[N];
int n, q;
int solve(LL b, LL e)
{
// cout << "(" << b << " " << e << ") : ";
bool rmc = true;
int res = 0;
vector<LL> removed;
while (b < e)
{
auto it = vals.lower_bound(b);
if (it == vals.begin())
{
rmc = false;
break;
}
it--;
if (it != vals.end())
{
b += *it;
// cout << *it << " ";
removed.PB(*it);
vals.erase(it);
res++;
}
else
{
rmc = false;
break;
}
}
// cout << "\n";
for (auto x : removed)
vals.insert(x);
if (!rmc)
return -1;
return res;
}
int main()
{
#ifndef local_comp
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n;
FOR (i, 1, n)
{
cin >> tab[i];
vals.insert(tab[i]);
}
cin >> q;
FOR (i, 1, q)
{
int type;
LL x, y;
cin >> type >> x;
if (type == 1)
cin >> y;
switch (type)
{
case 1:
cout << solve(x, y) << "\n";
break;
case 2:
vals.insert(x);
break;
case 3:
vals.erase(vals.find(x));
break;
}
}
return 0;
}
|