#include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); ll sim[limit], ext[limit]; struct seg { ll x1, x2, a, b; seg(ll x1, ll x2, ll a, ll b) :x1{x1}, x2{x2}, a{a}, b{b} { } ll cnt() { return -(a * (ext[x2] - ext[max(x1 - 1, 0ll)]) + b * (sim[x2] - sim[max(x1 - 1, 0ll)])); } ll intersect(ll a1, ll b1) { if(b1 - b >= x1 * (a - a1)) return (b1 - b) / (a - a1); return -inf; } }; int main(){ ll n, m, t1; scanf("%lld%lld", &n, &m); rep(i, 0, n) { scanf("%lld", &t1); sim[t1]++; ext[t1] += t1; } rep(i, 1, limit) { sim[i] += sim[i - 1]; ext[i] += ext[i - 1]; } vector<seg> border = {seg(-limit, limit - 1, 0, 0)}; rep(i, 0, m) { ll sum_under_border = 0; ll d, b; scanf("%lld%lld", &d, &b); while(true) { seg s = border.back(); border.pop_back(); sum_under_border += s.cnt(); ll c = s.intersect(-d, b); if(c >= limit) { border.pb(s); break; } if(c != -inf) { seg s1 = seg(s.x1, c, s.a, s.b), s2 = seg(c + 1, limit - 1, -d, b); sum_under_border -= s1.cnt(); printf("%lld\n", s2.cnt() - sum_under_border); border.pb(s1); border.pb(s2); 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 | #include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); ll sim[limit], ext[limit]; struct seg { ll x1, x2, a, b; seg(ll x1, ll x2, ll a, ll b) :x1{x1}, x2{x2}, a{a}, b{b} { } ll cnt() { return -(a * (ext[x2] - ext[max(x1 - 1, 0ll)]) + b * (sim[x2] - sim[max(x1 - 1, 0ll)])); } ll intersect(ll a1, ll b1) { if(b1 - b >= x1 * (a - a1)) return (b1 - b) / (a - a1); return -inf; } }; int main(){ ll n, m, t1; scanf("%lld%lld", &n, &m); rep(i, 0, n) { scanf("%lld", &t1); sim[t1]++; ext[t1] += t1; } rep(i, 1, limit) { sim[i] += sim[i - 1]; ext[i] += ext[i - 1]; } vector<seg> border = {seg(-limit, limit - 1, 0, 0)}; rep(i, 0, m) { ll sum_under_border = 0; ll d, b; scanf("%lld%lld", &d, &b); while(true) { seg s = border.back(); border.pop_back(); sum_under_border += s.cnt(); ll c = s.intersect(-d, b); if(c >= limit) { border.pb(s); break; } if(c != -inf) { seg s1 = seg(s.x1, c, s.a, s.b), s2 = seg(c + 1, limit - 1, -d, b); sum_under_border -= s1.cnt(); printf("%lld\n", s2.cnt() - sum_under_border); border.pb(s1); border.pb(s2); break; } } } return 0; } |