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
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

typedef long long LL;

#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MP make_pair
#define ST first
#define ND second
#define PB push_back
#define FOR(i,b,e) for(int i=(b); i<=(e); ++i)
#define FORD(i,b,e) for(int i=(b); i>=(e); --i)
#define REP(i,n) for(int i=0; i<n; ++i)
#define VAR(v,n) __typeof(n) v = (n)
#define SIZE(x) ((int)(x).size())
#define FOREACH(i,x) for(VAR(i,(x).begin()); i!=(x).end(); ++i)
#define SC scanf
#define PR printf

#define MAXM 500002

int tr[MAXM];
LL sum[MAXM];
map<int, pair<LL,LL> > koszenia;

typedef map<int, pair<LL,LL> >::iterator iter;

int kos(int d, LL t, LL h){
    iter it = koszenia.upper_bound(d);
    --it;
    return h < it->ND.ND+(t-it->ND.ST)*tr[d];
}

int main() {
    int n,m;
    LL t,h,last;
    SC("%d %d", &n, &m);
    REP(i,n) SC("%d", tr+i);

    sort(tr,tr+n);

    sum[n] = 0;
    sum[n-1] = tr[n-1];
    FORD(i,n-2,0) sum[i]=sum[i+1]+tr[i];

    koszenia.insert(MP(0,MP(0,0)));

    REP(i,m){
        scanf("%lld %lld", &t, &h);
        int b=0, e=n-1;
        while (b < e)
        {
            int d = (b+e)/2;
            if(kos(d,t,h))
                e = d;
            else
                b = d+1;
        }
        if(!kos(e,t,h))
            printf("0\n");
        else {
            LL res = 0;
            iter it = koszenia.upper_bound(e);
            it--;
            last = n;
            iter itrem = koszenia.end();
            itrem--;
            for(; itrem != it; --itrem){
                res+=(last-itrem->ST)*(itrem->ND.ND-h)+(sum[itrem->ST]-sum[last])*(t-itrem->ND.ST);
                last=itrem->ST;
            }
            res+=(last-e)*(it->ND.ND-h)+(sum[e]-sum[last])*(t-it->ND.ST);
            printf("%lld\n", res);

            if(it->ST!=e) ++it;
            koszenia.erase(it, koszenia.end());
            koszenia.insert(MP(e,MP(t,h)));
        }
    }
    return 0;
}