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

using namespace std;
#define MAX 500100
#define I unsigned long long
#define D(x)
#define D2(x)
#define dout cout

int n,m;
unsigned a[MAX];
I sum[MAX];


struct Skosz {
    Skosz(int poz, I d, I b):poz(poz),d(d),b(b){};
    Skosz(){};
    int poz;
    I d;
    I b;
};
vector<Skosz> stack;
I d, b;

I getH(int poz, Skosz &c) {
    I h = (d-c.d)*a[poz]+c.b;
    D2(dout << "getH(" << poz << ") = " << h << "\n");
    return h;
}

int znajdz_do(int x, int y, Skosz &c) {
    if(x==y) return x;
    int s = (x+y)/2;
    I h = getH(s, c);
    D2(dout << "znajdz_do(" << x << " ,[" << s << ":" << h << "], " << y << ")\n");
    if(h >= b) return znajdz_do(s+1,y,c);
    return znajdz_do(x,s,c);
}
I oblicz(int x, int y, Skosz &c) {
    I s = sum[y] - sum[x];
    I w = s*(d-c.d) + (y-x)*(c.b-b);
    return w;
}

I oblicz_w() {
    I w = 0;
    int od = 0;
    Skosz c;
    D(dout << "d:" << d << " b:" << b << "\n");
    while(!stack.empty()) {
        c = stack.back();
        if(getH(c.poz-1, c) >= b) {
            w+= oblicz(od, c.poz, c);
            D(dout << "remove:" << ", od:" << od << " ,do:" << c.poz  << " ,d:" << c.d << "\n");
            stack.pop_back();
            od=c.poz;
        } else {
            break;
        }
    }
	int poz = znajdz_do(od, c.poz, c);
	D(dout << "poz:" << poz << ", od:" << od << " ,do:" << c.poz << "\n");
	if(poz != 0) {
		w+= oblicz(od, poz, c);
		stack.push_back(Skosz(poz,d,b));
	}
    return w;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;i++) {
        scanf("%u",&a[i]);
    }
    sort(a, a+n, greater<unsigned>());
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        sum[i]=sum[i-1]+a[i-1];
    }
    stack.push_back(Skosz(n, 0, 0));
    while(m--) {
        scanf("%llu %llu",&d,&b);
        printf("%llu\n", oblicz_w());
        //return 0;
    }
}