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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

#define DEBUG

#ifdef DEBUG
#undef DEBUG
#endif

long long n, m;
long long glob_d, glob_b, prev_d;
//typedef pair<long long, long long> val_type;
typedef struct {
    long long p;
    long long d;
} val_type;
typedef map<long long, val_type > map_type;
typedef pair<long long, val_type > elem_type;
map_type M;
long long A[500001];
long long Asum[500001];
long long hay, prev_hay;

map_type::iterator it, it2;

long long calculate_height(long long field_index, long long base_height,
                           long long base_day, long long current_day) {
    return (base_height + (current_day - base_day)*A[field_index]);
}

int main() {
    long long i, j;

    scanf("%lld%lld", &n, &m);

    for (i=0; i<n; i++) {
        scanf("%lld", &A[i]);
    }

    sort(A, A+n);
    Asum[n-1] = A[n-1];
    for (i=n-2; i>=0; i--) {
        Asum[i] = Asum[i+1] + A[i];
    }

#ifdef DEBUG
    printf("Sorted:");
    for (i=0; i<n; i++) {
        printf(" %lld", A[i]);
    }
    printf("\n\n");

    printf("Sum:");
    for (i=0; i<n; i++) {
        printf(" %lld", Asum[i]);
    }
    printf("\n\n");
#endif

    /* Inserting initial base and day */
    val_type initial_day = { .p = 0, .d = 0 };
    M[0] = initial_day;

    /* Getting m input data */
    for (j=0; j<m; j++) {
        scanf("%lld%lld", &glob_d, &glob_b);

        /* find field_index element for which field_height is >= b */
        long long przed_a = 0;
        long long przed_b = n-1;
        long long field_height;
        long long field_index = n / 2;
        long long base_index, base_day, base_height;
        while (1) {
            field_index = (przed_b - przed_a) / 2 + przed_a;
            it = M.upper_bound(field_index);

            /* There should be not such situation, that we get M[0], as elements are [0-n), and we are looking for heigher than */
            assert(it != M.begin());
            /* upper_bound returns always bigger than field_index, decrement to get <= requested field_index */
            it--;

            /* Assign for readability */
            base_index = it->first;
            base_height = it->second.p;
            base_day = it->second.d;

            field_height = calculate_height(field_index, base_height, base_day, glob_d);
#ifdef DEBUG
            printf("\tbound(%lld) = %lld =>(p=%lld, d=%lld)\n", field_index, base_index, base_height, base_day);
            printf("field_height=%lld b=%lld\n", field_height, glob_b);
#endif
            if ( field_height < glob_b) {
                /* We can safely forget about field_index element, as we will not cut anything there */
                przed_a = field_index < przed_b ? field_index+1 : przed_b;
            } else {
                /* We need to cut this, so it's not a good idea to forget about field_index */
                przed_b = field_index;
            }
#ifdef DEBUG
            printf("new (a,b) = (%lld,%lld)\n", przed_a, przed_b);
#endif
            if (przed_a == przed_b) {
                field_index = przed_a;
                break;
            }
        }
#ifdef DEBUG
        printf("\tNew field_index value = %lld\n", field_index);
#endif

        /* Increment current hay value (before cutting) */
        hay += Asum[0]*(glob_d - prev_d);
        prev_hay = hay;
#ifdef DEBUG
        printf("# prev_hay=%lld\n", prev_hay);
#endif

        if (calculate_height(field_index, base_height, base_day, glob_d) < glob_b) {
#ifdef DEBUG
            printf("We have not exceeded glob_b value, continueing\n");
            printf("Cutted ");
#endif
            /* Printing current cut result */
            printf("0\n");
            continue;
        }

        /* Add new M element from based on current cut value (glob_b) and current day (glob_d) */
        val_type new_val = {
            .p = glob_b,
            .d = glob_d
        };
        pair<map_type::iterator, bool> new_elem = M.insert(elem_type(field_index, new_val));
        it = new_elem.first;
#ifdef DEBUG
        printf("Trying to insert p=%lld, d=%lld, success=%s\n", it->second.p, it->second.d, (new_elem.second ? "true" : "false"));
#endif

        long long prev_n = n;

        /* Remove all M values from the end to current field_index */
        it2 = M.end();
        it2--;
        for (; it2 != it; it2--) {
            long long height, day, index;
            height = it2->second.p;
            day = it2->second.d;
            index = it2->first;

            long long tmp = height*(prev_n - index) // base
                + (glob_d - day)*(Asum[index]-Asum[prev_n]); // above base
#ifdef DEBUG
            printf("Erasing1: height=%lld day=%lld Asum[%lld]=%lld\n", height, day, index, Asum[index]);
            printf("#0# removing %lld\n", tmp);
#endif
            hay -= tmp;

            /* Erase from M */
            M.erase(it2);

            /* Remember at which index we have stopped */
            prev_n = index;
        }
        
        if (!new_elem.second) {
            /* Replace element on field_index with new one */
            long long height, day, index;
            height = it->second.p;
            day = it->second.d;
            index = it->first;

            long long base = height*(prev_n - index);
            long long above = (glob_d - day)*(Asum[index]-Asum[prev_n]);
            long long tmp = base // base
                + above; // above base
#ifdef DEBUG
            printf("Erasing2: height=%lld day=%lld Asum[%lld]=%lld\n", height, day, index, Asum[index]);
            printf("#1# removing %lld  base=%lld above=%lld\n", tmp, base, above);
#endif
            hay -= tmp;

            /* Update element in M with new one */
            it->second = new_val;
            height = it->second.p;
            day = it->second.d;

            tmp = height*(n - index); // only base
#ifdef DEBUG
            printf("#1# adding %lld\n", tmp);
#endif
            hay += tmp;
        } else {
            /* Add new element, calculate hay based on found base_index */
            long long height, day, index;

            /* We calculate based on previous element in M */
            it--;
            index = it->first;
            height = it->second.p;
            day = it->second.d;
#ifdef DEBUG
            printf("Previous element in M height=%lld day=%lld index=%lld\n", height, day, index);
#endif

            long long base = height*(prev_n - field_index);
            long long above = (glob_d - day)*(Asum[field_index]-Asum[prev_n]);
            long long tmp = base + above;
#ifdef DEBUG
            printf("#2# removing %lld   base=%lld above=%lld\n", tmp, base, above);
#endif
            hay -= tmp;

            tmp = glob_b*(n - field_index); // only base
#ifdef DEBUG
            printf("#2# adding %lld\n", tmp);
#endif
            hay += tmp;
        }
#ifdef DEBUG
        printf("hay=%lld cutted=%lld\n", hay, prev_hay-hay);
#else
        printf("%lld\n", prev_hay - hay);
#endif

#ifdef DEBUG
        printf("M:");
        for (it=M.begin(); it!=M.end(); it++) {
            printf(" %lld => (p=%lld:d=%lld);", it->first, it->second.p, it->second.d);
        }
        printf("\n\n");
#endif

        prev_d = glob_d;
    }
}