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

using namespace std;

struct Mowing {
  Mowing(int64_t when, int64_t height, int maxIndex)
    : when(when), height(height), maxIndex(maxIndex) {}
  int64_t when, height;
  int maxIndex;
};

const int MAXN = 500009;

int n, m, maxIndex;
int64_t when, height, result;
int64_t growth[MAXN], growthPrefixRaw[MAXN];
int64_t* growthPrefix = growthPrefixRaw + 1;
stack<Mowing> lastMowings;

void initialize() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  growthPrefix[-1] = 0;
  for (int i = 0; i < n; i++) {
    cin >> growth[i];
  }
  sort(growth, growth + n, std::greater<int64_t>());
  for (int i = 0; i < n; i++) {
    growthPrefix[i] = growthPrefix[i - 1] + growth[i];
  }
  lastMowings.push(Mowing(0, 0, n - 1));
}

int binSearch(int down, int up) {
  const auto& lastMowing = lastMowings.top();
  while (up > down) {
    int middle = (down + up + 1) / 2;
    if (lastMowing.height + (when - lastMowing.when) * growth[middle] >= height) {
      down = middle;
    } else {
      up = middle - 1;
    }
  }
  return down;
}

int64_t growthInterval(int down, int up) {
  return growthPrefix[up] - growthPrefix[down - 1];
}

void computeMaxIndex() {
  if (lastMowings.empty()) {
    return;
  }
  const auto& lastMowing = lastMowings.top();
  int newMaxIndex = binSearch(maxIndex, lastMowing.maxIndex);
  result += growthInterval(maxIndex + 1, newMaxIndex) * (when - lastMowing.when);
  result -= (newMaxIndex - maxIndex) * (height - lastMowing.height);
  maxIndex = newMaxIndex;
}

int main() {
  initialize();
  while (m--) {
    cin >> when >> height;
    result = 0;
    maxIndex = -1;
    while (!lastMowings.empty() &&
        height < lastMowings.top().height) {
      const auto& lastMowing = lastMowings.top();
      int newMaxIndex = lastMowing.maxIndex;
      result += growthInterval(maxIndex + 1, newMaxIndex) * (when - lastMowing.when);
      result -= (newMaxIndex - maxIndex) * (height - lastMowing.height);
      maxIndex = newMaxIndex;
      lastMowings.pop();
    }
    
    computeMaxIndex();
    while (!lastMowings.empty() &&
        maxIndex == lastMowings.top().maxIndex) {
      lastMowings.pop();
      computeMaxIndex();
    }
    if (maxIndex >= 0) {
      lastMowings.push(Mowing(when, height, maxIndex));
    }

    cout << result << endl;
  }
}