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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename TH>
void debug_vars(const char* data, TH head){
    cerr << data << "=" << head << "\n";
}

template<typename TH, typename... TA>
void debug_vars(const char* data, TH head, TA... tail){
    while(*data != ',') cerr << *data++;
    cerr << "=" << head << ",";
    debug_vars(data+1, tail...);
}

#ifdef LOCAL
#define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#endif

/////////////////////////////////////////////////////////


const int MaxLen = 500005,
          MaxQ   = 500005;

int length, numQueries;
LL speeds[MaxLen];
LL speedsPref[MaxLen];   // sumy prefiksowe po klosach

void input(){
    scanf("%d%d", &length, &numQueries);
    for(int i = 1; i <= length; i++){
        scanf("%lld", &speeds[i]);
    }
    sort(speeds+1, speeds+length+1);
}

void precomp(){
    speedsPref[0] = 0;
    for(int i = 1; i <= length; i++){
        speedsPref[i] = speedsPref[i-1] + speeds[i];
    }
}

int main(){
    input();
    precomp();

    // pary sa postaci (x,t,h): ostatnie ciecie w czasie t dotyczylo
    // klosow o pozycjach co najmniej x i scielo je do wysokosci h
    vector<tuple<LL,LL,LL>> lastCut;
    lastCut.emplace_back(0,0,0);


    for(int query = 0; query < numQueries; query++){
        LL cTime, cHeight;
        scanf("%lld%lld", &cTime, &cHeight);

        // znajdujemy: pozycje pierwszego scietego klosa oraz laczna
        // wysokosc klosow

        LL lastFound = length+1;  // pierwszy od lewej sciety klos w operacji
        LL sumCuts   = 0;         // laczna wysokosc

        while(lastCut.size() > 0){
            LL cutPos, cutTime, cutHeight;
            tie(cutPos, cutTime, cutHeight) = *lastCut.rbegin();
            LL diffTime   = cTime - cutTime;
            LL diffHeight = cHeight - cutHeight;

            // jak szybko klos musi rosnac, bysmy mogli go sciac?
            LL needSpeed;
            if(diffHeight <= 0){  // scinamy nie wyzej, wiec i tak zetniemy wszystko
                needSpeed = 0;
            } else {
                // scinamy wyzej, musi byc ceil(dh / dt)
                needSpeed = (diffHeight+diffTime-1) / diffTime;
            }
            //debug(needSpeed);

            // znajdujemy pierwszy klos do sciecia
            LL firstCut = distance(speeds,
                    lower_bound(speeds+1, speeds+length+1, needSpeed));
            firstCut = max(firstCut, cutPos);   // na te chwile tniemy tylko dotad

            // czy juz to scielismy? wtedy skonczylismy z cieciem
            if(firstCut >= lastFound) break;

            // dodajemy do wyniku laczna wysokosc; jest to:
            // (suma predkosci na [firstCut,lastFound-1])*dt
            //      - (dlugosc przedzialu) * diffHeight
            LL speedAddend  = (speedsPref[lastFound-1] - speedsPref[firstCut-1]) * diffTime,
               heightAddend = (lastFound-firstCut) * diffHeight;

            sumCuts += (speedAddend - heightAddend);

            lastFound = firstCut;

            // nie zostalo nic niescietego? zrzucamy ze "stosu"
            if(firstCut <= cutPos){
                lastCut.pop_back();
            } else {
                // koniec przechodzenia
                break;
            }
        }

        // wrzucamy nasz przedzial
        if(lastFound <= length){
            lastCut.emplace_back(lastFound, cTime, cHeight);
        }

        printf("%lld\n", sumCuts);

        /*debug(query);
        for(auto& C : lastCut){
            LL x, t, h;
            tie(x,t,h) = C;
            debug(x, t, h);
        }*/

        //lastTime = cTime;
    }
}