#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) using LL = long long; const int N = 5e5; int a[N]; LL asum[N+1]; int n, m; struct S { int begin; int end; LL d; LL b; LL value(int i, LL t) const{ return a[i] * (t - d) + b; } S(int _begin, int _end, LL _d, LL _b):begin(_begin), end(_end), d(_d), b(_b){} }; int binsearch(S const &s, LL t, LL b){ assert(s.begin < s.end); if(s.value(s.begin, t) >= b){return s.begin;} if(s.value(s.end-1, t) < b){return s.end;} int lo = s.begin; int hi = s.end - 1; while(hi - lo > 1){ int mi = (lo + hi) / 2; ((s.value(mi, t) >= b) ? hi : lo) = mi; } return hi; } int main(){ assert(scanf("%d%d", &n, &m) == 2); REP(i, n) assert(scanf("%d", &a[i]) == 1); sort(a, a + n); asum[0] = 0; REP(i, n) asum[i+1] = asum[i] + a[i]; vector<S> v = {S(0, n, 0, 0)}; REP(i, m) { LL d, b; assert(scanf("%lld%lld", &d, &b) == 2); LL w = 0; while(!v.empty() && v.back().value(v.back().begin, d) >= b){ S s = v.back(); v.pop_back(); w += (asum[s.end] - asum[s.begin]) * (d - s.d) + (s.b - b) * (s.end - s.begin); } if(!v.empty()){ S s = v.back(); int j = binsearch(s, d, b); assert(j != s.begin); if(j != s.end){ w += (asum[s.end] - asum[j]) * (d - s.d) + (s.b - b) * (s.end - j); v.back().end = j; } } int begin = v.empty() ? 0 : v.back().end; if(begin != n){ v.push_back(S(begin, n, d, b)); } printf("%lld\n", w); } }
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 | #include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) using LL = long long; const int N = 5e5; int a[N]; LL asum[N+1]; int n, m; struct S { int begin; int end; LL d; LL b; LL value(int i, LL t) const{ return a[i] * (t - d) + b; } S(int _begin, int _end, LL _d, LL _b):begin(_begin), end(_end), d(_d), b(_b){} }; int binsearch(S const &s, LL t, LL b){ assert(s.begin < s.end); if(s.value(s.begin, t) >= b){return s.begin;} if(s.value(s.end-1, t) < b){return s.end;} int lo = s.begin; int hi = s.end - 1; while(hi - lo > 1){ int mi = (lo + hi) / 2; ((s.value(mi, t) >= b) ? hi : lo) = mi; } return hi; } int main(){ assert(scanf("%d%d", &n, &m) == 2); REP(i, n) assert(scanf("%d", &a[i]) == 1); sort(a, a + n); asum[0] = 0; REP(i, n) asum[i+1] = asum[i] + a[i]; vector<S> v = {S(0, n, 0, 0)}; REP(i, m) { LL d, b; assert(scanf("%lld%lld", &d, &b) == 2); LL w = 0; while(!v.empty() && v.back().value(v.back().begin, d) >= b){ S s = v.back(); v.pop_back(); w += (asum[s.end] - asum[s.begin]) * (d - s.d) + (s.b - b) * (s.end - s.begin); } if(!v.empty()){ S s = v.back(); int j = binsearch(s, d, b); assert(j != s.begin); if(j != s.end){ w += (asum[s.end] - asum[j]) * (d - s.d) + (s.b - b) * (s.end - j); v.back().end = j; } } int begin = v.empty() ? 0 : v.back().end; if(begin != n){ v.push_back(S(begin, n, d, b)); } printf("%lld\n", w); } } |