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
#include <cstdio>
#include <algorithm>

struct grupa {
    unsigned long long dzien;
    unsigned long long baza;
    unsigned id;
};

unsigned n,m;
unsigned * szybkosc;
unsigned long long * dzien;
unsigned long long * wysokosc;
unsigned long long * suma;
grupa * koszenia;

unsigned nGrup;
unsigned long long aktDzien;

grupa * badana;

bool porownajEl(const unsigned long long & a, const unsigned long long & val) {
    return ((badana->baza + (aktDzien-badana->dzien)*a) < val);
}

bool porownajGrupy(const grupa & a, const unsigned long long & b) {
    return ((a.baza + (aktDzien - a.dzien)*szybkosc[a.id]) < b);
}

unsigned maxIndex(const grupa * const a) {
    unsigned id = a - koszenia + 1;
    if (id < nGrup)
        return koszenia[id].id;
    else
        return n;
}

unsigned long long uzysk(const unsigned down, const unsigned up, unsigned long long h, grupa * g) {
    unsigned long long dolnaSuma;
    if (down == 0)
        dolnaSuma = 0;
    else
        dolnaSuma = suma[down-1];
    unsigned long long pozostawione = (up-down) * h;
    unsigned long long calosc = (suma[up-1]-dolnaSuma)*(aktDzien - g->dzien) + (up-down)*g->baza;
    return calosc - pozostawione;
}

int main(void) {
    scanf("%u %u", &n, &m);
    szybkosc = new unsigned[n+1];

    for (unsigned i=0u; i<n; i++)
        scanf("%u", (szybkosc+i));
    
    std::sort(szybkosc, (szybkosc+n));

    suma = new unsigned long long[n+1];
    suma[0] = szybkosc[0];
    for (unsigned i=1; i<n; i++)
        suma[i] = szybkosc[i] + suma[i-1];

    dzien = new unsigned long long[m+1];
    wysokosc = new unsigned long long[m+1];

    for (unsigned i=0u; i<m; i++)
        scanf("%llu %llu", (dzien+i), (wysokosc+i));

    koszenia = new grupa[m+1];
    koszenia[0] = {0u, 0u, 0};
    nGrup = 1;

    for (unsigned i=0u; i<m; i++) {
        aktDzien = dzien[i];
        grupa * res = std::lower_bound(koszenia, (koszenia+nGrup), wysokosc[i], porownajGrupy);
        if ( res == (koszenia+nGrup)) {
            res = (koszenia+nGrup-1);
        }
        unsigned * start = szybkosc+(res->id);
        if ((res != koszenia) && (*start >= wysokosc[i])) {
            badana = res-1;
            auto resMaly = std::lower_bound((szybkosc+badana->id), (szybkosc+res->id), wysokosc[i], porownajEl);
            if (*resMaly >= wysokosc[i]) {
                start = resMaly;
                res = res - 1;
            }
        } else if (*start < wysokosc[i]) {
            badana = res;
            unsigned upper_bound = maxIndex(res);
            auto resMaly = std::lower_bound((szybkosc+res->id), (szybkosc+upper_bound), wysokosc[i], porownajEl);
            if (resMaly == (szybkosc+n)) {
                printf("0\n");
                continue;
            }
            start = resMaly;
        }

        unsigned int indexGrupy = res - koszenia;
        unsigned int indexEl = start - szybkosc;

        unsigned long long res_suma = uzysk(indexEl, maxIndex(res), wysokosc[i], res);

        for (unsigned j = indexGrupy+1; j<nGrup; j++)
            res_suma += uzysk(koszenia[j].id, maxIndex(koszenia+j), wysokosc[i], koszenia+j);

        printf("%llu\n", res_suma);
        
        if (koszenia[indexGrupy].id == indexEl)
            koszenia[indexGrupy] = { dzien[i], wysokosc[i], indexEl };
        else {
            nGrup = indexGrupy+2;
            koszenia[indexGrupy+1] = { dzien[i], wysokosc[i], indexEl };
        }
    }

    return 0;
}