#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; int szczupak(map<unsigned long long,unsigned long long> &m, unsigned long long s, unsigned long long k) { int r=0; map<unsigned long long,unsigned long long> tmp; while(s<k && !m.empty() && m.begin()->first<s) { auto it = m.lower_bound(s); //printf("%llu %llu %d\n",s,it->first,it==m.end()); unsigned long long cel = it == m.end()?k:it->first+1; cel = cel>k?k:cel; it--; unsigned long long ile = (cel-s-1) / (it->first)+1; ile = ile > it->second ? it->second : ile; //printf("cel:%llu s:%llu cel-s:%llu first:%llu ile:%llu\n",cel,s,cel-s,it->first,ile); s+=it->first * ile; it->second-=ile; tmp[it->first]+=ile; if(it->second==0)m.erase(it); r+=ile; /* it--; s+=it->first; it->second--; if(it->second==0)m.erase(it); r++; */ } for(auto it = tmp.begin();it!=tmp.end();it++) { m[it->first]+=it->second; } if(s>=k)return r; else return -1; } int main() { // your code goes here unsigned long long n; unsigned long long w,sum=0; scanf("%llu",&n); map<unsigned long long,unsigned long long>m; for(unsigned long long i =0;i<n;i++) { scanf("%llu",&w); m[w]++; sum+=w; } unsigned long long q; scanf("%llu",&q); for(unsigned long long i=0;i<q;i++) { int c; scanf("%d",&c); switch(c) { case 1: unsigned long long s,k; scanf("%llu%llu",&s,&k); if(k<=s)printf("0\n"); else if(k-s>sum) printf("-1\n"); else printf("%d\n",szczupak(m,s,k)); break; case 2: scanf("%llu",&w); m[w]++; sum+=w; break; case 3: scanf("%llu",&w); m[w]--; if(m[w]==0)m.erase(w); sum-=w; break; } } 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 | #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; int szczupak(map<unsigned long long,unsigned long long> &m, unsigned long long s, unsigned long long k) { int r=0; map<unsigned long long,unsigned long long> tmp; while(s<k && !m.empty() && m.begin()->first<s) { auto it = m.lower_bound(s); //printf("%llu %llu %d\n",s,it->first,it==m.end()); unsigned long long cel = it == m.end()?k:it->first+1; cel = cel>k?k:cel; it--; unsigned long long ile = (cel-s-1) / (it->first)+1; ile = ile > it->second ? it->second : ile; //printf("cel:%llu s:%llu cel-s:%llu first:%llu ile:%llu\n",cel,s,cel-s,it->first,ile); s+=it->first * ile; it->second-=ile; tmp[it->first]+=ile; if(it->second==0)m.erase(it); r+=ile; /* it--; s+=it->first; it->second--; if(it->second==0)m.erase(it); r++; */ } for(auto it = tmp.begin();it!=tmp.end();it++) { m[it->first]+=it->second; } if(s>=k)return r; else return -1; } int main() { // your code goes here unsigned long long n; unsigned long long w,sum=0; scanf("%llu",&n); map<unsigned long long,unsigned long long>m; for(unsigned long long i =0;i<n;i++) { scanf("%llu",&w); m[w]++; sum+=w; } unsigned long long q; scanf("%llu",&q); for(unsigned long long i=0;i<q;i++) { int c; scanf("%d",&c); switch(c) { case 1: unsigned long long s,k; scanf("%llu%llu",&s,&k); if(k<=s)printf("0\n"); else if(k-s>sum) printf("-1\n"); else printf("%d\n",szczupak(m,s,k)); break; case 2: scanf("%llu",&w); m[w]++; sum+=w; break; case 3: scanf("%llu",&w); m[w]--; if(m[w]==0)m.erase(w); sum-=w; break; } } return 0; } |