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
#include <stdio.h>
#include <algorithm>
#include <set>

int szybkosc[500000];
long long suma_przyrostow_w_prawo[500001];

int powierzchnia, ileskoszen;
int i;

long long dzien_koszenia, wysokosc_koszenia;

struct Koszenie{
    int pierwszy_ciety;
    long long dzien_koszenia;
    long long wysokosc_koszenia;
    long long ilosc_trawy;

    Koszenie(int pierwszy_ciety, long long dzien_koszenia=0, long long wysokosc_koszenia=0, long long ilosc_trawy=0):
        pierwszy_ciety(pierwszy_ciety), dzien_koszenia(dzien_koszenia), wysokosc_koszenia(wysokosc_koszenia), ilosc_trawy(ilosc_trawy)
    {
    }
    bool operator<(const Koszenie& inne) const
    {
        return pierwszy_ciety < inne.pierwszy_ciety;
    }
};

std::set<Koszenie> koszenia;
typedef std::set<Koszenie>::iterator IteratorKoszenia;

inline long long wysokosc_trawy(int i)
{
    IteratorKoszenia it = koszenia.lower_bound(Koszenie(i));
    if (it==koszenia.end() || it->pierwszy_ciety>i)
    {
        it--;
    }

    return it->wysokosc_koszenia + (dzien_koszenia - it->dzien_koszenia) * (long long)(szybkosc[i]);
}

int licz_pierwszy_koszony()
{
    int count = powierzchnia;
    int left = 0;
    
    //printf("wysokosci:\n");
    //for(int i=0;i<powierzchnia; i++)
    //printf("%d ", wysokosc_trawy(i));
    

    while(count > 0)
    {
        int step = count/2;
        int middle = left+step;
        if(wysokosc_trawy(middle)<=wysokosc_koszenia)
        {
            left = middle+1;
            count -= step+1;
        }
        else
        {
            count = step;
        }
    }
    return left;
}


int main()
{
    scanf("%d%d", &powierzchnia, &ileskoszen);
    for(i=0; i<powierzchnia; i++)
    {
        scanf("%d", &szybkosc[i]);
    }


    std::sort(szybkosc, szybkosc+powierzchnia);
    for(i=powierzchnia-1; i>=0; i--)
    {
        suma_przyrostow_w_prawo[i] = suma_przyrostow_w_prawo[i+1] + szybkosc[i];
    }

    koszenia.insert(Koszenie(-1, 0, 0, 0));

    for(i=0; i<ileskoszen; i++)
    {
        scanf("%lld%lld", &dzien_koszenia, &wysokosc_koszenia);

        int pierwszy_koszony = licz_pierwszy_koszony();
        IteratorKoszenia pierwsze_koszenie_po_prawej = koszenia.lower_bound(Koszenie(pierwszy_koszony));
        IteratorKoszenia ostatnie_koszenie_po_lewej = pierwsze_koszenie_po_prawej;
        ostatnie_koszenie_po_lewej--;

        long long ilosc_trawy_z_koszeniami_po_prawej = ostatnie_koszenie_po_lewej->wysokosc_koszenia * (powierzchnia - pierwszy_koszony);
        ilosc_trawy_z_koszeniami_po_prawej += suma_przyrostow_w_prawo[pierwszy_koszony] * (dzien_koszenia - ostatnie_koszenie_po_lewej->dzien_koszenia);
        ilosc_trawy_z_koszeniami_po_prawej -= wysokosc_koszenia * (powierzchnia - pierwszy_koszony);

        long long ilosc_trawy = ilosc_trawy_z_koszeniami_po_prawej;

        for(IteratorKoszenia it=pierwsze_koszenie_po_prawej; it!=koszenia.end(); it++)
        {
            ilosc_trawy -= it->ilosc_trawy;
        }
        //printf("pierwszy_koszony %d, ilosc_trawy_z_koszeniami_po_prawej %lld\n", pierwszy_koszony, ilosc_trawy_z_koszeniami_po_prawej);

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

        koszenia.erase(pierwsze_koszenie_po_prawej, koszenia.end());

        koszenia.insert(Koszenie(pierwszy_koszony, dzien_koszenia, wysokosc_koszenia, ilosc_trawy_z_koszeniami_po_prawej));
    }
}