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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class Cut {
 public:
  Cut() : left_(0), base_(0), day_(0) {}
  Cut(const int left, const long long base, const long long day)
      : left_(left), base_(base), day_(day) {}

  int left() const { return left_; }

  long long GetWeight(const Cut& cut, const vector<long long>& sums) const {
    if (left_ >= sums.size()) return 0;
    return sums[left_] * (day_ - cut.day_) -
        (base_ - cut.base_) * (sums.size() - left_);
  }

  bool IsAbove(
      const vector<int>& a, const long long d, const long long b) const {
    if (left_ >= a.size()) return true;
    return GetHeight(a, d, left_) >= b;
  }

  Cut SubCut(const vector<int>& a, const long long d, const long long b) const {
    // TODO: This is a linear function, can be done in O(1).
    int left = left_;
    int right = a.size();
    while (left + 1 < right) {
      const int m = (left + right) / 2;
      if (GetHeight(a, d, m) <= b) left = m + 1; else right = m;
    }
    if (GetHeight(a, d, left) <= b) ++left;
    // cerr << "New cut " << left << ' ' << b << ' ' << d << endl;
    return Cut(left, b, d);
  }

 private:
  long long GetHeight(
      const vector<int>&a, const long long d, const int i) const {
    return base_ + a[i] * (d - day_);
  }

  int left_;
  long long base_;
  long long day_;
};

int main() {
  int n;
  int m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  sort(a.begin(), a.end());

  // Init structures.
  stack<Cut> s;
  s.push(Cut());

  vector<long long> sums(n);
  sums[n - 1] = a[n - 1];
  for (int i = n - 1; i > 0; --i) sums[i - 1] = sums[i] + a[i - 1];

  while (m--) {
    long long d;
    long long b;
    scanf("%lld%lld", &d, &b);

    long long w = 0;

    // Undo cuts covered by the current one.
    while (s.size() > 1 && s.top().IsAbove(a, d, b)) {
      const Cut cut = s.top();
      s.pop();
      w -= cut.GetWeight(s.top(), sums);
    }

    // Add current cut.
    const Cut cut = s.top().SubCut(a, d, b);
    w += cut.GetWeight(s.top(), sums);
    s.push(cut);

    printf("%lld\n", w);
  }

  return 0;
}