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
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int a, n, m;
vector<long long> v, sum; //v_rosn, sumy_prefix
long long d, b;
map<long long, long long> d_wys; //mapa dzien -> sciecie
vector<pair<long long, long long> > stos; //stos cięć, zawiera id początku ścięcia

void dodaj(pair<long long, long long> p) {
    while(!stos.empty() && stos.back().second >= p.second) {
       stos.pop_back();
    }
    stos.push_back(p);
}

long long ost_ciecie(int id) { //to da się zrobić lepiej
    int s = stos.size() - 1;
    while(s >= 0 && stos[s].second > id) {
        s--;
    }
    if(s >= 0) return stos[s].first;
    return 0;
}


long long oblicz_wynik(int id, long long d) {
    long long wynik = 0;
    int s = stos.size() - 1;
    int ost = n;
    while(s >= 0 && stos[s].second >= id) {
        wynik = wynik + (d - stos[s].first) * (sum[ost] - sum[stos[s].second]);
        wynik = wynik + d_wys[stos[s].first] * (ost - stos[s].second);
        ost = stos[s].second;
        s--;
    }
    if(ost != id) 
        wynik = wynik + d * (sum[ost] - sum[id]) ;
        if(!stos.empty() && s >= 0) {
            wynik = wynik - stos[s].first * (sum[ost] - sum[id]); 
            wynik = wynik + d_wys[stos[s].first] * (ost - id);
        }
    return wynik;
}

int binary_search(int p, int k, long long d, long long b) {
    int curr_score = 500001;
    while(p < k) {
        int x = (p+k)/2;
         if (( (d - ost_ciecie(x))*v[x] + d_wys[ost_ciecie(x)]) > b) {
            k = x;
            curr_score = min(curr_score, x);
         }
         else {
            p = x + 1;
         }
    }
    return curr_score;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; ++i) {
        scanf("%d",&a);
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    
    sum.push_back(0);
    
    for(int i = 0; i < n; ++i){
        sum.push_back(sum.back() + v[i]);
    }
    
    for(int i = 0; i < m; ++i) {
        scanf("%lld%lld",&d, &b);
        d_wys[d] = b;
        
        long long wynik = 0;
        int x = binary_search(0, n-1, d , b);
        if(x != 500001) {
            wynik = oblicz_wynik(x, d);
            wynik = wynik - b * (n - x);
            dodaj(make_pair(d, x));
        }
        printf("%lld\n", wynik);
    }
    return 0;
}