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

#ifdef DBG
	const bool dbg = true;
#else
	const bool dbg = false;
#endif

using namespace std;

const int MAX_N = 500000;

typedef unsigned long long ull;

struct Drzewo {
	int szyb_wzrostu;
	int ilosc_takich, ilosc_wiekszych;
	ull wysokosc_sciecia;
	ull ostatnie_ciecie;
	ull suma_wiekszych;
	Drzewo *lsyn;
	Drzewo *psyn;
};

void wypiszDrzewo(Drzewo * d) {
	if (!dbg) return;
	printf("(%d, %d, %d, %llu, %llu, %llu, %s, %s)\n", d->szyb_wzrostu, d->ilosc_takich, d->ilosc_wiekszych, d->wysokosc_sciecia, d->ostatnie_ciecie,
			d->suma_wiekszych, d->lsyn ? "JEST" : "NIE MA", d->psyn ? "JEST" : "NIE MA");
}

void wypiszDrzewoRek(Drzewo * d) {
	if (!dbg) return;
	wypiszDrzewo(d);
	if (d->lsyn) wypiszDrzewoRek(d->lsyn);
	if (d->psyn) wypiszDrzewoRek(d->psyn);
}

ull poprz_dzien = 0, dzien = 1, suma = 0, wys;
int n, m;

int a[MAX_N+1];
vector<Drzewo> szybkosci;

Drzewo * wektorDoDrzewa(vector<Drzewo> w, int pocz, int kon) {
	if (pocz > kon) return NULL;
	
	int s = (pocz + kon) / 2;
	Drzewo *d = &w[s];
	d->lsyn = wektorDoDrzewa(w, pocz, s - 1);
	d->psyn = wektorDoDrzewa(w, s + 1, kon);
	return d;
}

ull faktycznyKlucz(Drzewo * d, ull dzien) {
	return d->szyb_wzrostu * (dzien - d->ostatnie_ciecie) + d->wysokosc_sciecia;
}

Drzewo * znajdzPierwszeWieksze(Drzewo * d, ull dzien, ull wysokosc) {
	if (d == NULL)
		return NULL;

	if (faktycznyKlucz(d, dzien) > wysokosc) {
		Drzewo *inny = znajdzPierwszeWieksze(d->lsyn, dzien, wysokosc);
		d->ostatnie_ciecie = dzien;
		d->wysokosc_sciecia = wysokosc;
		return inny == NULL ? d : inny;
	}

	if (d->psyn != NULL && d->psyn->ostatnie_ciecie < d->ostatnie_ciecie) {
		d->psyn->ostatnie_ciecie = d->ostatnie_ciecie;
		d->psyn->wysokosc_sciecia = d->wysokosc_sciecia;
	}
	return znajdzPierwszeWieksze(d->psyn, dzien, wysokosc);
}

int main() {
	scanf("%d %d", &n, &m);
	int tmp_szybkosc;
	
	// zerujemy tablice
	for (int i = 1; i < n + 1; i++) {
		a[i] = 0;
	}

	// zliczamy ile czego jest
	for (int i = 0; i < n; i++) {
		scanf("%d", &tmp_szybkosc);
		if (dbg) printf("%d\n", tmp_szybkosc);
		a[tmp_szybkosc]++;
	}

	int j;

	// wrzucamy unikalne szybkosci do wektora
	for (int i = 1; i < n + 1; i++) {
		if (a[i] != 0) {
			szybkosci.push_back({ i, a[i], 0, 0, 0, 0, NULL, NULL  });
			if (dbg) printf("%d\n", szybkosci[szybkosci.size()-1].szyb_wzrostu);
		}
	}
	
	// sortujemy
	//sort(szybkosci.begin(), szybkosci.end(), [] (Drzewo a, Drzewo b) { return a.szyb_wzrostu < b.szyb_wzrostu;  });

	// sumy prefixowe (suma plonow i ilosci wyzszych)
	int kw = szybkosci.size() - 1;

	szybkosci[kw].suma_wiekszych = szybkosci[kw].szyb_wzrostu * szybkosci[kw].ilosc_takich;
	szybkosci[kw].ilosc_wiekszych = 0;
	for (int i = szybkosci.size() - 2; i >= 0; i--) {
		szybkosci[i].suma_wiekszych = szybkosci[i].szyb_wzrostu * szybkosci[i].ilosc_takich + szybkosci[i+1].suma_wiekszych;
		szybkosci[i].ilosc_wiekszych = szybkosci[i+1].ilosc_takich + szybkosci[i+1].ilosc_wiekszych;
	}

	if (dbg) {
		for (int d = 0; d < szybkosci.size(); d++)
			printf("(%d, %d, %d, %llu), ", szybkosci[d].szyb_wzrostu, szybkosci[d].ilosc_takich, szybkosci[d].ilosc_wiekszych, szybkosci[d].suma_wiekszych);
		printf("\n");
	}

	// drzewo BST by szybciej wyszukiwac
	Drzewo * d = wektorDoDrzewa(szybkosci, 0, szybkosci.size() - 1);
	
	wypiszDrzewoRek(d);

	Drzewo * tmp;
	ull dzisiejsza_suma;
	for (int i = 0; i < m; i++) {
		scanf("%llu %llu", &dzien, &wys);
		tmp = znajdzPierwszeWieksze(d, dzien, wys);
		if (tmp == NULL) {
			printf("0\n");
		} else {
			dzisiejsza_suma = (tmp->suma_wiekszych * dzien) - suma - (tmp->ilosc_wiekszych + 1) * wys;
			printf("%llu\n", dzisiejsza_suma);
			suma += dzisiejsza_suma;
			wypiszDrzewoRek(d);
		}
	}
}