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

using namespace std;

const int N=500000;
int a[N+1];
long long pref[N+2]; // pref[i]=a[0]+...+a[i-1]

struct block {
    long long d;
    long long b;
    long long s; // początek bloku b

    block(int dd, int bb, int ss) : d(dd), b(bb), s(ss) {}
};
vector<block> field;

long long intSum(int i, int j) {
    //suma el. a od i do j-1
    return pref[j]-pref[i];
}

int findIndex(int i,int j,long long d_coef,long long b_coef,long long b) {
    while(i + 1 < j) {
       int middle=(i+j)/2;
       if(a[middle]*d_coef+b_coef <= b ) i=middle;
       else j=middle;
    }
    return i;
}

long long harvest(long long b, int n) {
    int j=field.size()-2; // gwarantujemy ze field.size() >=2
    long long d_coef=0;
    long long cut=0;
    long long b_coef;

    while(true) {
       d_coef+=field[j+1].d;
       b_coef=field[j].b;
       if(a[field[j].s]*d_coef+b_coef <= b) break;
       cut+=d_coef*intSum(field[j].s,field[j+1].s)
            +b_coef*(field[j+1].s-field[j].s);
       field.pop_back();
       --j;
    }
    // k - ostatni indeks gdzie trawa[i] <= b
    int k=findIndex(field[j].s,field[j+1].s,d_coef,b_coef,b);
    ++k; // odtąd tniemy

    cut+=d_coef*intSum(k,field[j+1].s)+b_coef*(field[j+1].s-k);
    field[j+1].b=b;
    field[j+1].d=d_coef;
    field[j+1].s=k;

    cut-=(n-k)*b; // tniemy do wys. b

    return cut;
}

int main() {
    int n,m;
    scanf("%d",&n); ++n;
    scanf("%d",&m);
    a[0]=0; // wartownik
    for(int i=1; i<n; ++i) scanf("%d",a+i);
    sort(a,a+n);

    pref[0]=0;
    for (int i=0; i<n; ++i) pref[i+1]=pref[i]+a[i];

    long long d_prev=0;
    field.push_back(block(0,0,0)); //wartownik
    for (int i=0; i<m; ++i) {
       long long b,d;
       scanf("%lld",&d);
       scanf("%lld",&b);

       if((d-d_prev)*a[n-1]+field.back().b > b) {
          field.push_back(block(d-d_prev,0,n));
          long long cut = harvest(b,n);
          d_prev=d;
          printf("%lld\n",cut);
       }
       else printf("%d\n",0);
    }

    return 0;
}