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
#include<bits/stdc++.h>
#define ul unsigned long long
using namespace std;
ul wzrost[1000005];
ul pre[1000005];
ul il[1000005];
ul stos[1000005][4];
ul dzien=0;
ul ile[1000005];
int main(){
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        ul x;
        scanf("%llu", &x);
        ile[x]++;
    }
    for(int i=1; i<=1000000; i++)
    {
        ul h=i;
        pre[i]=pre[i-1]+ile[i]*h;
    }
    for(int i=1; i<=1000000; i++)
    {
        il[i]=il[i-1]+ile[i];
    }
    int g=0;
    for(int i=1; i<=m; i++){
        ul d,b;
        scanf("%llu%llu", &d, &b);
        dzien=d;
        int x=1000001;
        g++;
        ul w=0;
        stos[g][0]=x;
        stos[g][3]=0;
        while(g>1 && stos[g-1][2]+(dzien-stos[g-1][1])*stos[g-1][0]>=b )
        {
            x=stos[g-1][0];
            w+=stos[g-1][3];
            g--;
        }
        ul b2=stos[g-1][2];
        b2=b-b2;
        ul h=dzien-stos[g-1][1];
        ul y=(b2+h-1)/h;

        if(y<x)
            x=y;
        else
        {
            w-=stos[g][3];
            g++;
        }
        //printf("%llu %llu\n", x, w);
        stos[g][0]=x;
        stos[g][1]=dzien;
        stos[g][2]=b;
        ul pp=n-il[x-1];
        ul wyn=(dzien-stos[g-1][1])*(pre[1000000]-pre[x-1])+stos[g-1][2]*pp;
        wyn-=w;
        printf("%llu\n", wyn-b*pp);
        stos[g][3]=w+wyn-pp*b;
    }
}