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
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <tuple>

using namespace std;

int max_szybkosc = 1000000;


void wczytaj_pola (int n, vector<int>& licznosc_pol, vector<long long>& przyrost_trawy)
{
    int szybkosc_przyrostu; // szybkosc pola = dzienny przyrost trawy

    licznosc_pol = vector<int>(max_szybkosc,0); // licznosc_pol[ii-1] to liczba pol
    // o dziennym przyroscie trawy >= ii ; ii nalezy do [1, 10^6]

    przyrost_trawy = vector<long long>(max_szybkosc,0); // przyrost_trawy[ii-1]
    // to suma skumulowana przyrostu trawy na wszystkich polach o przyroscie dziennym >= ii

    for (int ii=0; ii<n; ii++)
    {
        cin>>szybkosc_przyrostu;
        licznosc_pol[szybkosc_przyrostu-1] +=1;
        przyrost_trawy[szybkosc_przyrostu-1] +=szybkosc_przyrostu;
    }

    licznosc_pol.push_back(0);
    przyrost_trawy.push_back(0);
    // 0 pol o szybkosci 1000001, ale latwiej robic przedzialy

    for (vector<int>::reverse_iterator it=licznosc_pol.rbegin()+1; it!=licznosc_pol.rend(); ++it)
        *it += *(it-1); // suma skumulowana licznosci pol

    for (vector<long long>::reverse_iterator it=przyrost_trawy.rbegin()+1;
         it!=przyrost_trawy.rend(); ++it)
        *it += *(it-1); // suma skumulowana przyrostu trawy
}


int szukaj_pocz_koszenia(int pocz, int kon, long long ile_dni, long long wys_ost,
                         long long wys_koszenia)
{
    long long stan_trawy;
    int srod;
    while(pocz<kon)
    {
        srod = (pocz+kon)/2;
        stan_trawy = wys_ost + ile_dni*srod;
        if (stan_trawy==wys_koszenia)
            return srod;
        else if (stan_trawy>wys_koszenia)
            kon=srod;
        else
            pocz=srod+1;
    }
    return pocz;
}



long long skoszone_siano(long long dzien_koszenia, long long wys_koszenia, const vector<int>& licznosc_pol,
                         const vector<long long>& przyrost_trawy,
                         map<int, pair<long long, long long> >& koszenia)
{
    long long siano=0, stan_trawy, dzien_ost=0, wys_ost=0;
    int szybkosc, pocz=1, kon = przyrost_trawy.size(); // granice szybkosci pola do przeszukania binarnego

    for(auto rev_it=koszenia.rbegin(); rev_it!=koszenia.rend(); ++rev_it)
    {
        szybkosc = rev_it->first; // min szybkosc pola w ostatnim koszeniu
        tie(dzien_ost,wys_ost) = rev_it->second;
        stan_trawy = wys_ost + (dzien_koszenia-dzien_ost)*szybkosc;
        if (stan_trawy >= wys_koszenia)
        {
            // siano = trawa pozostala po ostanim koszeniu + trawa przyrosla od ostaniego
            // koszenia - trawa pozostajaca po obecnym koszeniu
            siano += (wys_ost - wys_koszenia) *(licznosc_pol[szybkosc-1] - licznosc_pol[kon-1]) +
                (dzien_koszenia - dzien_ost) *(przyrost_trawy[szybkosc-1] - przyrost_trawy[kon-1]);
            kon = szybkosc;
            // usuwanie z tabeli pamietanego poprzedniego koszenia obecnie koszonej trawy:            
        }
        else
        {
            pocz = szybkosc;
            //szukanie skoszonego siana w przedziale o wspolnym starcie
            pocz = szukaj_pocz_koszenia(pocz,kon, dzien_koszenia-dzien_ost, wys_ost, wys_koszenia);
            siano += (wys_ost - wys_koszenia) *(licznosc_pol[pocz-1] - licznosc_pol[kon-1]) +
                    (dzien_koszenia - dzien_ost) *(przyrost_trawy[pocz-1] - przyrost_trawy[kon-1]);

            //dodanie  wpisu do tabeli koszen:
            koszenia[pocz] = make_pair(dzien_koszenia, wys_koszenia);
            auto it=koszenia.upper_bound(pocz);
            koszenia.erase(it, koszenia.end());

            return siano;
        }
    }

    dzien_ost=0; wys_ost=0;
    //szukanie skoszonego siana w przedziale o wspolnym starcie
    pocz = szukaj_pocz_koszenia(pocz,kon, dzien_koszenia-dzien_ost, wys_ost, wys_koszenia);
    siano += (wys_ost - wys_koszenia) *(licznosc_pol[pocz-1] - licznosc_pol[kon-1]) +
            (dzien_koszenia - dzien_ost) *(przyrost_trawy[pocz-1] - przyrost_trawy[kon-1]);

    //dodanie  wpisu do tabeli koszen:
    koszenia[pocz] = make_pair(dzien_koszenia, wys_koszenia);
    auto it=koszenia.upper_bound(pocz);
    koszenia.erase(it, koszenia.end());

    return siano;
}




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

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

    int n, m;
    long long dzien, wys_koszenia;

    cin>>n >>m;

    vector<int> licznosc_pol; // licznosc_pol[ii-1] to suma skumulowana liczby pol
    // o dziennym przyroscie trawy >= ii ; ii nalezy do [1, 10^6]

    vector<long long> przyrost_trawy; // przyrost_trawy[ii-1] to suma skumulowana
    // przyrostu trawy na wszystkich polach o dziennym przyroscie >= ii

    wczytaj_pola(n, licznosc_pol, przyrost_trawy);

    map<int, pair<long long, long long> > koszenia;
    //mapa p->(d,b), gdzie d to dzien koszenia trawy;
    // p to dzienny przyrost trawy na najwolniejszym polu skoszonym w dniu d; b to wysokosc koszenia


    for (int jj = 0; jj<m; jj++)
    {
        cin>>dzien >>wys_koszenia;

        long long siano = skoszone_siano(dzien, wys_koszenia, licznosc_pol,
                                         przyrost_trawy, koszenia);
        cout<<siano<<endl;

    }

    return 0;
}