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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct schodek {
	int poczatek;
	long long dzien, wysokosc;
	
	schodek(int poczatek, long long dzien, long long wysokosc) {
		this->poczatek = poczatek;
		this->dzien = dzien;
		this->wysokosc = wysokosc;
	}
};

vector<int> szybkosc;
vector<long long> sumy_prefiksowe_szybkosci;
vector<schodek> schodki;

long long wysokosc_trawy(int nr_schodka, int pozycja, long long dzien) {
	return schodki[nr_schodka].wysokosc + (dzien - schodki[nr_schodka].dzien) * szybkosc[pozycja];
}

long long suma_wysokosci(int nr_schodka, int pocz, int kon, long long dzien, long long wys) {
	return (kon - pocz + 1) * (schodki[nr_schodka].wysokosc - wys) + 
		(sumy_prefiksowe_szybkosci[kon] - sumy_prefiksowe_szybkosci[pocz] + szybkosc[pocz]) * (dzien - schodki[nr_schodka].dzien);
}

int koniec_schodka(int nr_schodka) {
	if (nr_schodka == schodki.size() - 1)
		return szybkosc.size() - 1;
	return schodki[nr_schodka + 1].poczatek - 1;
}

long long rozwiaz(long long dzien, long long wys) {
	if (wys >= wysokosc_trawy(schodki.size() - 1, szybkosc.size() - 1, dzien))
		return 0;
	int nr_schodka = schodki.size() - 1;
	while (nr_schodka > 0 && wys <= wysokosc_trawy(nr_schodka, schodki[nr_schodka].poczatek, dzien))
		nr_schodka--;
	if (nr_schodka < schodki.size() - 1 && wys > wysokosc_trawy(nr_schodka, schodki[nr_schodka + 1].poczatek - 1, dzien))
		nr_schodka++;
	int lewy = schodki[nr_schodka].poczatek;
	int prawy = koniec_schodka(nr_schodka);
	while (lewy < prawy) {
		int x = (lewy + prawy) / 2;
		if (wys > wysokosc_trawy(nr_schodka, x, dzien))
			lewy = x + 1;
		else
			prawy = x;
	}
	long long suma = 0;
	suma += suma_wysokosci(nr_schodka, lewy, koniec_schodka(nr_schodka), dzien, wys);
	for (int i = nr_schodka + 1; i < schodki.size(); ++i)
		suma += suma_wysokosci(i, schodki[i].poczatek, koniec_schodka(i), dzien, wys);
	int koncowy = schodki.size() - 1;
	int poczatkowy = nr_schodka + 1;
	if (lewy == schodki[nr_schodka].poczatek)
		poczatkowy = nr_schodka;
	for (int i = koncowy; i >= poczatkowy; --i)
		schodki.pop_back();
	schodki.push_back(schodek(lewy, dzien, wys));
	return suma;
}

int main() {
	int n, m, i;
	long long dzien, wys;
	scanf("%d%d", &n, &m);
	szybkosc.resize(n, 0);
	sumy_prefiksowe_szybkosci.resize(n, 0);
	for (i = 0; i < n; ++i)
		scanf("%d", &szybkosc[i]);
	sort(szybkosc.begin(), szybkosc.end());
	sumy_prefiksowe_szybkosci[0] = szybkosc[0];
	for (i = 1; i < n; ++i)
		sumy_prefiksowe_szybkosci[i] = sumy_prefiksowe_szybkosci[i - 1] + szybkosc[i];
	schodki.push_back(schodek(0, 0, 0));
	for (i = 0; i < m; ++i) {
		scanf("%lld%lld", &dzien, &wys);
		printf("%lld\n", rozwiaz(dzien, wys));
	}
	return 0;
}