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

using namespace std;

int T1[1000001];
unsigned long long int T[500001];
unsigned long long int pole[500001][3];


int main()
{
    long long int n,m;
    cin >> n >> m;

    unsigned long long int nr;

    if (n<90000){
        for (int i=0; i<n; i++){
            cin >> T[i];
        }
        sort(&T[0],&T[n]);
        nr = 0;
        pole[0][0] = T[0];
        pole[0][1] = 1;
        pole[0][2] = 0;
        for (int i=1; i<n; i++){
            if (T[i] == T[i-1]){
                pole[nr][1]++;
            }
            else{
                nr++;
                pole[nr][0] = T[i];
                pole[nr][1] = 1;
                pole[nr][2] = 0;
            }
        }
        nr++;
    }
    else{
        int maxi = 0;
        for (int i=0; i<n; i++){
            int x;
            cin >> x;
            T1[x]++;
            if (x > maxi) maxi = x;
        }
        nr = 0;
        for (int i=0; i<=maxi; i++){
            if (T1[i] > 0){
                pole[nr][0] = i;
                pole[nr][1] = T1[i];
                pole[nr][2] = 0;
                nr++;
            }
        }

    }

    unsigned long long int d;
    unsigned long long int b;
    unsigned long long int ile = 0;
    unsigned long long int d1 = 0;

    for (int i=0; i<m; i++){
        cin >> d >> b;

        for (int j=0; j<nr; j++){
            pole[j][2] += pole[j][0]*(d-d1);
            if (pole[j][2] > b){
                ile += pole[j][2]-b;
                pole[j][2] = b;
            }
        }
        cout << ile << endl;
        ile = 0;
        d1 = d;
    }

}