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
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
#include <map>

using namespace std;

using i64 = int64_t;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  i64 n, m;
  cin >> n >> m;

  vector<i64> a(n);
  i64 sum_a = 0;
  for (i64& a_elem : a) {
    cin >> a_elem;
    sum_a += a_elem;
  }
  sort(a.begin(), a.end());

  // prefix_sums[k] = sum(0..k-1, a[i])
  vector<i64> prefix_sums(n+1);
  prefix_sums[0] = 0;
  for (int i = 0; i < n; ++i) {
    prefix_sums[i+1] = prefix_sums[i] + a[i];
  }
  assert(prefix_sums[n] == sum_a);

  // pos -> (d, height)
  using T = pair<int, pair<i64, i64>>;
  vector<T> cuts;
  cuts.reserve(m + 1);
  cuts.push_back(T(0, {0, 0}));

  for (int i = 0; i < m; ++i) {
    i64 day, b;
    cin >> day >> b;
    // cout << "day:" << day << " b:" << b << endl;

    auto GetHeight = [&](int i) {
      auto it = lower_bound(cuts.begin(), cuts.end(), T(i+1, {-1, -1}));
      assert(it == cuts.end() || it->first > i);
      assert(it != cuts.begin());
      --it;
      assert(it->first <= i);
      return a[i] * (day - it->second.first) + it->second.second;
    };

    int cut_pos = [&]{
      int lo = 0, hi = n;
      while (lo != hi) {
        int mid = (lo + hi) / 2;
        if (GetHeight(mid) < b) {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      }
      return hi;
    }();

    i64 harvest = 0;

    if (cut_pos != n) {
      int right = n;
      while (right != cut_pos) {
        assert(!cuts.empty());
        auto it = cuts.end();
        --it;
        i64 cut_day = it->second.first;
        i64 cut_height = it->second.second;
        int left = max(it->first, cut_pos);
        harvest += cut_height * (right - left)
                 + (day - cut_day) * (prefix_sums[right] - prefix_sums[left])
                 - b * (right - left);
        if (it->first >= left) {
          cuts.pop_back();
        }
        right = left;
      }
      cuts.push_back(T(cut_pos, {day, b}));
    }

    cout << harvest << '\n';
  }
}