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
// Potyczki Algorytmiczne 2015
// runda 1
// SIAno
// Tomasz Pastusiak

#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>

using namespace std;

#define MAX_M_N 500000
//#define MAX_M_N 5
//#define MAX_M_N 4

    long long int growthSpeed[MAX_M_N];
    long long int cutDays[MAX_M_N + 1]; // place for fake 0 height cut at day 0
    long long int cutHeights[MAX_M_N + 1]; // place for fake 0 height cut at day 0
    long long int cutAreas[MAX_M_N + 1]; // place for fake 0 height cut at day 0
    long long int areaGrowth[MAX_M_N + 1]; // total growth on area 0..(i-1)
    long long int totalWeights[MAX_M_N + 2]; // total weight cut grass after i'th cut (0 cuts give 0 grass), additional +1 for fake cut

// entries in the tree numbered from 1 to 2*n - 1
// base elements have numbers: n + 0 ..... n + n - 1
// information is stored on areas ( log(n) )
// information is retrieved from points by traversing to the root ( log(n) )
class AreaHeightDateTree{
public:
    long long int heightTree[MAX_M_N*2];
    long long int dateTree[MAX_M_N*2];
    long long int n;
    long long int size;

    void setSize(long long int n){
        this->n = n;
        size = 2*n;
        for(long long int i=1;i<size;++i){
            heightTree[i] = 0; // grass height at time 0 = 0
            dateTree[i] = 0;
        }
    }

    long long int getHeight(long long int position, long long int currentDate){
        long long int node = n + position;
        long long int storedHeight = heightTree[node];
        long long int storedDate = dateTree[node];

        while (node != 1) {
            node /= 2;
            if(dateTree[node] > storedDate){
                storedHeight = heightTree[node];
                storedDate = dateTree[node];
            }
        }

        long long int currentHeight = storedHeight + (currentDate - storedDate)*(long long int)growthSpeed[position];
        return currentHeight;
    } // get current height at position

    void setAreaHeight(long long int areaFrom, long long int areaTo, long long int height, long long int currentDate){
        long long int nl = n + areaFrom, nr = n + areaTo; // node left, node right

        heightTree[nl] = heightTree[nr] = height;
        dateTree[nl] = dateTree[nr] = currentDate;

        while (nl / 2 != nr / 2) {
         if (nl % 2 == 0){
            heightTree[nl + 1] = height;
            dateTree[nl + 1] = currentDate;
         } // if left node is left child of some parent, save info in right brother
         if (nr % 2 == 1){
            heightTree[nr - 1] = height;
            dateTree[nr - 1] = currentDate;
         } // if right node is right child of some parent, save info in left brother
         nl /= 2; nr /= 2;
        }
    }

    long long int getAreaHigherThan(long long int height, long long int currentDate){
        // use binary search
        long long int l = 0, r = n, mid;
        while(l != r){
            mid = (l + r)/2;
            long long int midHeight = getHeight(mid, currentDate);
            if(midHeight > height) l = mid + 1;
            else r = mid;
        }

        return l; // or r
    } // get Area higher than
};

AreaHeightDateTree ahdt;

int main(){
    ios_base::sync_with_stdio(false);

    long long int n, m;

    cin >> n >> m;

    for(long long int i=0; i<n ;++i){
        cin >> growthSpeed[i];
    }

    for(long long int i=0; i<m; ++i){
        cin >> cutDays[i] >> cutHeights[i];
    }

    // DATA LOADED

    // for algorithm to work, growthSpeed has to be sorted

    sort(growthSpeed, growthSpeed + n, greater<long long int>());
    areaGrowth[0] = 0; // area of size 0 do not grow at all
    for(long long int i=0; i<n ;++i){
        areaGrowth[i + 1] = areaGrowth[i] + growthSpeed[i];
    }

    ahdt.setSize(n);

    // lets calculate cut areas using AreaHeightDateTree

    for(long long int i=0; i<m; ++i){
        cutAreas[i] = ahdt.getAreaHigherThan(cutHeights[i], cutDays[i]);
        if(cutAreas[i] != 0){
            ahdt.setAreaHeight(0, cutAreas[i] - 1, cutHeights[i], cutDays[i]);
        }
    }

    cutAreas[MAX_M_N] = n; // fake cut at height 0, day 0, it cut whole area: n
    cutDays[MAX_M_N] = 0;
    cutHeights[MAX_M_N] = 0;
    totalWeights[MAX_M_N + 1] = 0;

    stack<long long int> descendingAreaCuts; // cut IDs on stack

    descendingAreaCuts.push(MAX_M_N); // adding fake cut on the bottom, no harm

    totalWeights[0] = 0;
    for(long long int i=0; i<m; ++i){
        while(cutAreas[descendingAreaCuts.top()] < cutAreas[i]) descendingAreaCuts.pop();

        long long int previousCutID = descendingAreaCuts.top();

        totalWeights[i + 1] = (cutDays[i] - cutDays[previousCutID])*areaGrowth[cutAreas[i]] - cutAreas[i]*(cutHeights[i]-cutHeights[previousCutID]) + totalWeights[previousCutID + 1];

        descendingAreaCuts.push(i);
    }

    // Based on total weights, calculate individual weights

    for(long long int i=0; i<m; ++i){
        cout << (totalWeights[i + 1] - totalWeights[i]) << '\n';
    }

    cout.flush();

    return 0;
}