#include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 5e5+100; multiset <ll> w; void add(ll a){ w.insert(a); } void del(ll a){ w.erase(w.find(a)); } int answer(ll a, ll b){ int ret = 0; vll toErase; while(a > b){ ret++; auto i = w.upper_bound(a); if(i == w.end()) break; toErase.pb(*i); a += *i; w.erase(i); } for(auto i = w.begin(); i != w.end() && a > b && *i > a; i++, ret++) a += *i; for(auto i: toErase) w.insert(i); if(a > b) return -1; return ret; } int main(){ int n; cin >> n; for(int i = 0; i < n; i++){ ll x; cin >> x; add(-x); } int q; cin >> q; while(q--){ int type; ll a, b; cin >> type; switch(type){ case 1: cin >> a >> b; cout << answer(-a, -b) << endl; break; case 2: cin >> a; add(-a); break; case 3: cin >> a; del(-a); break; } } }
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 | #include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 5e5+100; multiset <ll> w; void add(ll a){ w.insert(a); } void del(ll a){ w.erase(w.find(a)); } int answer(ll a, ll b){ int ret = 0; vll toErase; while(a > b){ ret++; auto i = w.upper_bound(a); if(i == w.end()) break; toErase.pb(*i); a += *i; w.erase(i); } for(auto i = w.begin(); i != w.end() && a > b && *i > a; i++, ret++) a += *i; for(auto i: toErase) w.insert(i); if(a > b) return -1; return ret; } int main(){ int n; cin >> n; for(int i = 0; i < n; i++){ ll x; cin >> x; add(-x); } int q; cin >> q; while(q--){ int type; ll a, b; cin >> type; switch(type){ case 1: cin >> a >> b; cout << answer(-a, -b) << endl; break; case 2: cin >> a; add(-a); break; case 3: cin >> a; del(-a); break; } } } |