#include <iostream> #include <map> #include <set> using namespace std; long long x,suma; map <long long,pair<int,pair<int,int> > > M; set <long long> SET; map <long long,pair<int,pair<int,int> > >::iterator it; set <long long>::iterator iter; int szczupak(long long m,long long k,int l) { iter=SET.end(); iter--; if(m<=-*iter) { return -1; } while(m<k) { iter=SET.upper_bound(-m); x=-*iter; it=M.find(x); if(M[it->first].second.second!=l) { M[it->first].second.second=l; M[it->first].second.first=M[it->first].first; } while((M[it->first].second.first==0)) { if(it==M.begin()) { return -1; } --it; if(M[it->first].second.second!=l) { M[it->first].second.second=l; M[it->first].second.first=M[it->first].first; } } m+=it->first; --M[it->first].second.first; ++suma; } return suma; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,p,z; long long m,k; cin>>n; for(int i=0;i<n;++i) { cin>>m; SET.insert(-m); ++M[m].first; } cin>>z; for(int i=1;i<=z;++i) { cin>>p; if(p==1) { cin>>m>>k; if(m>=k) { cout<<0<<"\n"; } else { suma=0; cout<<szczupak(m,k,i)<<"\n"; } } else if(p==2) { cin>>m; SET.insert(-m); ++M[m].first; } else { cin>>m; --M[m].first; if(M[m].first==0) { SET.erase(-m); } } } return 0; }
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 | #include <iostream> #include <map> #include <set> using namespace std; long long x,suma; map <long long,pair<int,pair<int,int> > > M; set <long long> SET; map <long long,pair<int,pair<int,int> > >::iterator it; set <long long>::iterator iter; int szczupak(long long m,long long k,int l) { iter=SET.end(); iter--; if(m<=-*iter) { return -1; } while(m<k) { iter=SET.upper_bound(-m); x=-*iter; it=M.find(x); if(M[it->first].second.second!=l) { M[it->first].second.second=l; M[it->first].second.first=M[it->first].first; } while((M[it->first].second.first==0)) { if(it==M.begin()) { return -1; } --it; if(M[it->first].second.second!=l) { M[it->first].second.second=l; M[it->first].second.first=M[it->first].first; } } m+=it->first; --M[it->first].second.first; ++suma; } return suma; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,p,z; long long m,k; cin>>n; for(int i=0;i<n;++i) { cin>>m; SET.insert(-m); ++M[m].first; } cin>>z; for(int i=1;i<=z;++i) { cin>>p; if(p==1) { cin>>m>>k; if(m>=k) { cout<<0<<"\n"; } else { suma=0; cout<<szczupak(m,k,i)<<"\n"; } } else if(p==2) { cin>>m; SET.insert(-m); ++M[m].first; } else { cin>>m; --M[m].first; if(M[m].first==0) { SET.erase(-m); } } } return 0; } |