#include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <iterator> #include <string> #include <vector> #include <queue> #include <bitset> #include <utility> #include <stack> #include <numeric> using namespace std; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; #define MP make_pair #define FOR(v,p,k) for(auto v=(p);v<=(k);++v) #define FORD(v,p,k) for(auto v=(p);v>=(k);--v) #define REP(i,n) for(auto i=0;i<(n);++i) #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define PB push_back #define ST first #define ND second #define SIZE(x) (int)x.size() #define ALL(c) c.begin(),c.end() #define ODD(x) ((x)%2) #define EVEN(x) (!(ODD(x))) int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<LL> sz(n); REP(i,n) { cin >> sz[i]; } sort(ALL(sz)); vector<LL> suf_sz = sz; partial_sum(suf_sz.rbegin(), suf_sz.rend(), suf_sz.rbegin()); //guards sz.push_back(0LL); suf_sz.push_back(0LL); vector<pair<LL,LL>> trims(m); REP(i,m) { cin >> trims[i].first >> trims[i].second; } stack<PII> last_trim; REP(t,m) { LL d = trims[t].first; LL b = trims[t].second; LL res{}; int last_trimmed_pos = n; while (!last_trim.empty()) { auto index = last_trim.top().first; auto trim_nr = last_trim.top().second; auto delta_d = d - trims[trim_nr].first; auto old_b = trims[trim_nr].second; if (sz[index] * delta_d + old_b >= b) { LL cnt = last_trimmed_pos - index; auto delta_suf_sz = suf_sz[index] - suf_sz[last_trimmed_pos]; res += cnt * (old_b - b) + delta_d * delta_suf_sz; last_trimmed_pos = index; last_trim.pop(); } else { auto it = lower_bound(sz.begin()+index, sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) { return (x * delta_d + old_b) < b; }); auto pos = it - sz.begin(); LL cnt = last_trimmed_pos - pos; auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos]; res += cnt * (old_b - b) + delta_d * delta_suf_sz; if (pos != n) last_trim.push(make_pair(pos, t)); last_trimmed_pos = pos; break; } } if (last_trim.empty()) { auto it = lower_bound(sz.begin(), sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) { return (x * d) < b; }); auto pos = it - sz.begin(); LL cnt = last_trimmed_pos - pos; auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos]; res += cnt * (0LL - b) + d * delta_suf_sz; if (pos != n) last_trim.push(make_pair(pos, t)); } cout << res << endl; } cout << flush; 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <cstdio> #include <cstring> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <iterator> #include <string> #include <vector> #include <queue> #include <bitset> #include <utility> #include <stack> #include <numeric> using namespace std; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; #define MP make_pair #define FOR(v,p,k) for(auto v=(p);v<=(k);++v) #define FORD(v,p,k) for(auto v=(p);v>=(k);--v) #define REP(i,n) for(auto i=0;i<(n);++i) #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define PB push_back #define ST first #define ND second #define SIZE(x) (int)x.size() #define ALL(c) c.begin(),c.end() #define ODD(x) ((x)%2) #define EVEN(x) (!(ODD(x))) int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<LL> sz(n); REP(i,n) { cin >> sz[i]; } sort(ALL(sz)); vector<LL> suf_sz = sz; partial_sum(suf_sz.rbegin(), suf_sz.rend(), suf_sz.rbegin()); //guards sz.push_back(0LL); suf_sz.push_back(0LL); vector<pair<LL,LL>> trims(m); REP(i,m) { cin >> trims[i].first >> trims[i].second; } stack<PII> last_trim; REP(t,m) { LL d = trims[t].first; LL b = trims[t].second; LL res{}; int last_trimmed_pos = n; while (!last_trim.empty()) { auto index = last_trim.top().first; auto trim_nr = last_trim.top().second; auto delta_d = d - trims[trim_nr].first; auto old_b = trims[trim_nr].second; if (sz[index] * delta_d + old_b >= b) { LL cnt = last_trimmed_pos - index; auto delta_suf_sz = suf_sz[index] - suf_sz[last_trimmed_pos]; res += cnt * (old_b - b) + delta_d * delta_suf_sz; last_trimmed_pos = index; last_trim.pop(); } else { auto it = lower_bound(sz.begin()+index, sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) { return (x * delta_d + old_b) < b; }); auto pos = it - sz.begin(); LL cnt = last_trimmed_pos - pos; auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos]; res += cnt * (old_b - b) + delta_d * delta_suf_sz; if (pos != n) last_trim.push(make_pair(pos, t)); last_trimmed_pos = pos; break; } } if (last_trim.empty()) { auto it = lower_bound(sz.begin(), sz.begin()+last_trimmed_pos, 42LL, [&](LL x, LL dummy) { return (x * d) < b; }); auto pos = it - sz.begin(); LL cnt = last_trimmed_pos - pos; auto delta_suf_sz = suf_sz[pos] - suf_sz[last_trimmed_pos]; res += cnt * (0LL - b) + d * delta_suf_sz; if (pos != n) last_trim.push(make_pair(pos, t)); } cout << res << endl; } cout << flush; return 0; } |