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

using namespace std;

int liczba_gatunkow;
int liczba_skoszen_trawy;

const int max_rozmiar = 500000+1;

long long int szybkosc_wzrostu[max_rozmiar+1];

long long int sumy_suf[max_rozmiar+1];
struct Kol{
    long long int wartosc;
    long long int pozycja;
    long long int ostatnie_koszenie;
};

void oblicz_sumy_suf(){
    sumy_suf[liczba_gatunkow-1] = szybkosc_wzrostu[liczba_gatunkow-1];
    for(int i = liczba_gatunkow-2; i >= 0; --i){
        sumy_suf[i] = sumy_suf[i+1]+szybkosc_wzrostu[i];
    }
}

int wyszukaj_binarnie(int pocz, int kon, long long int baza, long long int mnozenie, long long int min_wys){
    while(kon-pocz > 1){
        int srod = (kon+pocz)/2;
        if((baza + mnozenie*szybkosc_wzrostu[srod]) > min_wys){
            kon = srod;
        }else {
            pocz = srod;
        }
    }
    if((baza + mnozenie*szybkosc_wzrostu[pocz]) > min_wys){
        return pocz;
    }
    return kon;

}

void wczytaj(){
    cin >> liczba_gatunkow >> liczba_skoszen_trawy;
    for(int i = 0; i <liczba_gatunkow; ++i){
        cin >> szybkosc_wzrostu[i];
    }
    sort(szybkosc_wzrostu, szybkosc_wzrostu+liczba_gatunkow);
    oblicz_sumy_suf();
    stack<Kol> stos;
    Kol k1;
    k1.pozycja = 0;
    k1.wartosc = 0;
    k1.ostatnie_koszenie = 0;
    stos.push(k1);

    int poprzedni = 0;
    for(int i = 0; i < liczba_skoszen_trawy; ++i){
        long long int moj_dzien, wys_przyciecia;

        cin >> moj_dzien >> wys_przyciecia;

        long long int koniec_przedz = liczba_gatunkow;
        long long int do_doania = 0;

        //int wielkosc = stos.size();
       // int pocz = wielkosc? stos.top().wartosc : -123;

       // int haha = wielkosc? szybkosc_wzrostu[stos.top().pozycja] * (moj_dzien-poprzedni) + stos.top().wartosc : -123;
        //int beka = wielkosc? szybkosc_wzrostu[stos.top().pozycja] : -123;
        while(!stos.empty() && (szybkosc_wzrostu[stos.top().pozycja] * (moj_dzien-stos.top().ostatnie_koszenie) + stos.top().wartosc > wys_przyciecia)){
            int liczba_elementow = koniec_przedz-stos.top().pozycja;

            do_doania += (sumy_suf[stos.top().pozycja]-((koniec_przedz < liczba_gatunkow)?sumy_suf[koniec_przedz]:0))*(moj_dzien-stos.top().ostatnie_koszenie);
            do_doania += (liczba_elementow)*stos.top().wartosc;
            do_doania -= (liczba_elementow)*wys_przyciecia;
            koniec_przedz = stos.top().pozycja;
            stos.pop();
        }

        long long int sprawdz_nowe = (stos.empty())? -1 : stos.top().pozycja;
        long long int baza = (stos.empty())? -1 : stos.top().wartosc;
        long long int pocz_przedzialu = (koniec_przedz < liczba_gatunkow)? koniec_przedz : koniec_przedz-1;
        //cout << "przed wyszukiwaniem bin " << do_doania << " " << sprawdz_nowe << " " << koniec_przedz-1 << " " << moj_dzien-stos.top().ostatnie_koszenie << endl;

        if(sprawdz_nowe != -1){
            int bin = wyszukaj_binarnie(sprawdz_nowe, koniec_przedz-1, baza, moj_dzien-stos.top().ostatnie_koszenie, wys_przyciecia);
    //cout << "bin znalazl " << szybkosc_wzrostu[bin] << endl;

            if((baza + (moj_dzien-stos.top().ostatnie_koszenie)*szybkosc_wzrostu[bin]) > wys_przyciecia){
                long long int liczba_elementow = koniec_przedz-bin;
                do_doania += (sumy_suf[bin] - ((koniec_przedz < liczba_gatunkow)?sumy_suf[koniec_przedz]:0))*(moj_dzien-stos.top().ostatnie_koszenie);
                do_doania += (liczba_elementow)*baza;
                do_doania -= (liczba_elementow)*wys_przyciecia;
                pocz_przedzialu = bin;

            }
        }
        //cout << "po wyszukiwaniu bin " << do_doania << endl;



        cout << do_doania << endl;
        if(do_doania){
            Kol k2;
            k2.pozycja = pocz_przedzialu;
            k2.wartosc = wys_przyciecia;
            k2.ostatnie_koszenie = moj_dzien;
            stos.push(k2);
        }
        poprzedni = moj_dzien;
    }


}

void wypisz(){
    for(int i = 0; i <liczba_gatunkow; ++i){
        cout << szybkosc_wzrostu[i] << " ";
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    wczytaj();
    //wypisz();
    return 0;
}