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
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,i,p,t=1,le,ri,h,a[500500];
long long x,y,r,b[500500],c[500500],d[500500],s[500500];
int main() {
  scanf("%d%d",&n,&m); b[t]=n;
  for (i=1; i<=n; i++) scanf("%d",&a[i]);
  sort(a+1,a+n+1);
  reverse(a+1,a+n+1);
  for (i=1; i<=n; i++) s[i]=s[i-1]+a[i];
  while (m--) {
    scanf("%lld%lld",&x,&y);
    for (r=p=0; t>0 && a[b[t]]*(x-d[t])+c[t]>=y; t--) {
      r+=(s[b[t]]-s[p])*(x-d[t])+(c[t]-y)*(b[t]-p);
      p=b[t];
    }
    if (t>0) {
      le=p; ri=b[t];
      while (p<ri) {
        h=(p+ri)/2+1;
        if (a[h]*(x-d[t])+c[t]>=y) p=h; else ri=h-1;
      }
      r+=(s[ri]-s[le])*(x-d[t])+(c[t]-y)*(ri-le);
    }
    b[++t]=p; c[t]=y; d[t]=x;
    printf("%lld\n",r);
  }
  return 0;
}