#include <algorithm> #include <cstdio> #include <iostream> #include <stack> using namespace std; typedef long long ll; const int N_MAX = 5e5+10; const int T_MAX = 3*N_MAX; struct node { ll start, last_d, last_b; node(ll s, ll ld, ll lb) : start(s), last_d(ld), last_b(lb) {} void debug() { cerr << "node (" << start << ", " << last_d << ", " << last_b << ")\n"; } }; int n, m; ll a[N_MAX]; ll d, b; stack<node> s; ll sum_tree[T_MAX]; void build_sum_tree(int i, int x, int y) { if (x == y) { sum_tree[i] = a[x]; } else { int mid = (x+y) / 2; build_sum_tree(2*i, x, mid); build_sum_tree(2*i+1, mid+1, y); sum_tree[i] = sum_tree[2*i] + sum_tree[2*i+1]; } } ll val_sum_tree(int i, int l, int r, int x, int y) { if (x > y) return 0; if (l == x && r == y) return sum_tree[i]; int mid = (l+r) / 2; ll res = 0; res += val_sum_tree(2*i, l, mid, x, min(y, mid)); res += val_sum_tree(2*i+1, mid+1, r, max(mid+1, x), y); return res; } ll sum_between(ll x, ll y) { ll res = (x < n) ? val_sum_tree(1, 0, n-1, x, y-1) : 0; // cerr << "sum_between(" << x << ", " << y << ") = " << res << '\n'; return res; } ll sum_between_slow(ll x, ll y) { ll res = 0; for (int i = x; i < y; i++) { res += a[i]; } cerr << "sum_between_slow(" << x << ", " << y << ") = " << res << '\n'; return res; } ll find_k_slow(ll x, ll y, ll t_last_b, ll t_last_d) { for (ll k = x; k < y; k++) { if (t_last_b + (d - t_last_d) * a[k] > b) return k; } return y; } ll find_k(ll x, ll y, ll t_last_b, ll t_last_d) { ll count = y-x, step; while (count > 0) { // cerr << "find_k " << x << " " << (x+count) << '\n'; step = count / 2; ll mid = x + step; if (!(b < t_last_b + (d - t_last_d) * a[mid])) { x = mid+1; count -= step+1; } else { count = step; } } return x; } int main() { s.push(node(-1, 0, 0)); scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%lld", a+i); sort(a, a+n); build_sum_tree(1, 0, n-1); for (int qq = 0; qq < m; qq++) { scanf("%lld %lld", &d, &b); // cerr << "> " << d << " " << b << '\n'; ll ans = 0; ll k = n, r = n; while (!s.empty()) { node t = s.top(); // t.debug(); if ((t.start == -1) || (t.last_b + (d - t.last_d) * a[t.start] <= b)) { // cerr << "part\n"; // k = find_k_slow(t.start + 1, r, t.last_b, t.last_d); k = find_k(t.start + 1, r, t.last_b, t.last_d); ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b; // cerr << "ans=" << ans << '\n'; break; } else { // cerr << "full\n"; s.pop(); k = t.start; // cerr << "k..r=" << k << " " << r << '\n'; ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b; // cerr << "ans=" << ans << '\n'; r = k; } } if (k < n) s.push(node(k, d, b)); printf("%lld\n", ans); } 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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <algorithm> #include <cstdio> #include <iostream> #include <stack> using namespace std; typedef long long ll; const int N_MAX = 5e5+10; const int T_MAX = 3*N_MAX; struct node { ll start, last_d, last_b; node(ll s, ll ld, ll lb) : start(s), last_d(ld), last_b(lb) {} void debug() { cerr << "node (" << start << ", " << last_d << ", " << last_b << ")\n"; } }; int n, m; ll a[N_MAX]; ll d, b; stack<node> s; ll sum_tree[T_MAX]; void build_sum_tree(int i, int x, int y) { if (x == y) { sum_tree[i] = a[x]; } else { int mid = (x+y) / 2; build_sum_tree(2*i, x, mid); build_sum_tree(2*i+1, mid+1, y); sum_tree[i] = sum_tree[2*i] + sum_tree[2*i+1]; } } ll val_sum_tree(int i, int l, int r, int x, int y) { if (x > y) return 0; if (l == x && r == y) return sum_tree[i]; int mid = (l+r) / 2; ll res = 0; res += val_sum_tree(2*i, l, mid, x, min(y, mid)); res += val_sum_tree(2*i+1, mid+1, r, max(mid+1, x), y); return res; } ll sum_between(ll x, ll y) { ll res = (x < n) ? val_sum_tree(1, 0, n-1, x, y-1) : 0; // cerr << "sum_between(" << x << ", " << y << ") = " << res << '\n'; return res; } ll sum_between_slow(ll x, ll y) { ll res = 0; for (int i = x; i < y; i++) { res += a[i]; } cerr << "sum_between_slow(" << x << ", " << y << ") = " << res << '\n'; return res; } ll find_k_slow(ll x, ll y, ll t_last_b, ll t_last_d) { for (ll k = x; k < y; k++) { if (t_last_b + (d - t_last_d) * a[k] > b) return k; } return y; } ll find_k(ll x, ll y, ll t_last_b, ll t_last_d) { ll count = y-x, step; while (count > 0) { // cerr << "find_k " << x << " " << (x+count) << '\n'; step = count / 2; ll mid = x + step; if (!(b < t_last_b + (d - t_last_d) * a[mid])) { x = mid+1; count -= step+1; } else { count = step; } } return x; } int main() { s.push(node(-1, 0, 0)); scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%lld", a+i); sort(a, a+n); build_sum_tree(1, 0, n-1); for (int qq = 0; qq < m; qq++) { scanf("%lld %lld", &d, &b); // cerr << "> " << d << " " << b << '\n'; ll ans = 0; ll k = n, r = n; while (!s.empty()) { node t = s.top(); // t.debug(); if ((t.start == -1) || (t.last_b + (d - t.last_d) * a[t.start] <= b)) { // cerr << "part\n"; // k = find_k_slow(t.start + 1, r, t.last_b, t.last_d); k = find_k(t.start + 1, r, t.last_b, t.last_d); ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b; // cerr << "ans=" << ans << '\n'; break; } else { // cerr << "full\n"; s.pop(); k = t.start; // cerr << "k..r=" << k << " " << r << '\n'; ans += t.last_b * (r-k) + (d - t.last_d) * sum_between(k, r) - (r-k) * b; // cerr << "ans=" << ans << '\n'; r = k; } } if (k < n) s.push(node(k, d, b)); printf("%lld\n", ans); } return 0; } |