#include <map> #include <algorithm> #include <cstdio> #include <iostream> typedef long long int lli; struct A { lli h; lli d; }; typedef std::map<int,A> M; typedef std::pair<int,A> P; typedef M::iterator iter; const int max_n = 500500; int a[max_n]; lli s[max_n]; M mp; int n, m; lli G(int i, lli d) { iter lb = mp.upper_bound(i) ; lb --; const A& s = lb->second; return s.h+(d-s.d) * a[i]; } int lower_bound (int start, int end, lli h, lli d) { int it, step; int count = end - start; while (count>0) { it = start; step=count/2; it += step; if (G(it,d) < h) { start=++it; count-=step+1; } else count=step; } return start; } lli calc(lli d, lli h) { int lb = lower_bound(0,n, h, d); iter u = mp.upper_bound(lb); u --; const A& ss = u->second; lli r = ss.h*(n-lb)+(d-ss.d)*s[lb]-h*(n-lb); A q; q.h = h; q.d = d; P p(lb,q); if(u->first < lb) u ++; mp.erase(u, mp.end()); mp.insert(p); return r; } int main() { std::cin >> n >> m; for(int i=0; i<n; i++) std::cin >> a[i]; std::sort(a,a+n); s[n-1] = a[n-1]; for(int i=n-2;i>=0;i--) s[i] = a[i] + s[i+1]; A aa=A{0,0}; mp.insert(P(0,aa)); for(int i=0; i<m; i++) { lli d, b; std::cin >> d >> b; std::cout << calc(d, b) << std::endl; } 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 | #include <map> #include <algorithm> #include <cstdio> #include <iostream> typedef long long int lli; struct A { lli h; lli d; }; typedef std::map<int,A> M; typedef std::pair<int,A> P; typedef M::iterator iter; const int max_n = 500500; int a[max_n]; lli s[max_n]; M mp; int n, m; lli G(int i, lli d) { iter lb = mp.upper_bound(i) ; lb --; const A& s = lb->second; return s.h+(d-s.d) * a[i]; } int lower_bound (int start, int end, lli h, lli d) { int it, step; int count = end - start; while (count>0) { it = start; step=count/2; it += step; if (G(it,d) < h) { start=++it; count-=step+1; } else count=step; } return start; } lli calc(lli d, lli h) { int lb = lower_bound(0,n, h, d); iter u = mp.upper_bound(lb); u --; const A& ss = u->second; lli r = ss.h*(n-lb)+(d-ss.d)*s[lb]-h*(n-lb); A q; q.h = h; q.d = d; P p(lb,q); if(u->first < lb) u ++; mp.erase(u, mp.end()); mp.insert(p); return r; } int main() { std::cin >> n >> m; for(int i=0; i<n; i++) std::cin >> a[i]; std::sort(a,a+n); s[n-1] = a[n-1]; for(int i=n-2;i>=0;i--) s[i] = a[i] + s[i+1]; A aa=A{0,0}; mp.insert(P(0,aa)); for(int i=0; i<m; i++) { lli d, b; std::cin >> d >> b; std::cout << calc(d, b) << std::endl; } return 0; } |