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
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long LL;

#define PB push_back

const int MAX = 500000;

struct cut {
  LL day, height;
  int from;
};

int n, m;
LL arr[MAX], sum[MAX+1];
vector<cut> stack;

int main() {
  scanf("%d %d", &n, &m);
  for (int i=0;i<n;i++)
    scanf("%lld", arr+i);
  sort(arr, arr+n);
  for (int i=n-1;i>=0;i--)
    sum[i] = sum[i+1] + arr[i];
  stack.PB({0, 0, 0});
  while (m--)
  {
    LL d, h;
    scanf("%lld %lld", &d, &h);
    int last_from = n;
    LL res = 0;
    while (!stack.empty() && h <= stack.back().height + (d - stack.back().day) * arr[stack.back().from])
    {
      cut c = stack.back();
      res += (sum[c.from] - sum[last_from]) * (d - c.day);
      res += (c.height - h) * (last_from - c.from);
      last_from = c.from;
      stack.pop_back();
    }
    if (stack.empty()) {
      stack.PB({d, h, 0});
    } else {
      int lo = stack.back().from;
      int hi = last_from;
      while (lo + 1 < hi)
      {
        int mid = (lo + hi) / 2;
        LL hmid = stack.back().height + (d - stack.back().day) * arr[mid];
        if (hmid < h) lo = mid;
        else hi = mid;
      }
      res -= (h - stack.back().height) * (last_from - hi);
      res += (sum[hi] - sum[last_from]) * (d - stack.back().day);
      stack.PB({d, h, hi});
    }
    printf("%lld\n", res);
  }
  return 0;
}