Kyselyt

#include <bits/stdc++.h>
 
#define MAXPOW 19
#define MAX 200002
 
int n, q;
int luku[MAX];
int minimitaso[MAX];
long hinta_alusta[MAX];
long hinta_loppuun[MAX];
int max[MAX][MAXPOW];
int maxpos[MAX][MAXPOW];
 
std::pair<int, int> max_valilla(int a, int b) {
	int l = b - a;
	int pow = __builtin_ctz(l & -l);
	int p = a + (1 << pow);
	if (p != b) {
		auto r = max_valilla(p, b);
		if (r.first > max[p-1][pow]) {
			return r;
		}
	}
	return {max[p-1][pow], maxpos[p-1][pow]};
}
 
int main() {
	std::cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		std::cin >> luku[i];
 
		// Lasketaan taulukoihin tietoa lukuvälien maksimiluvuista.
		max[i][0] = luku[i];
		maxpos[i][0] = i;
		for (int p = 1; p < MAXPOW; ++p) {
			int j = i - (1 << (p - 1));
			max[i][p] = max[i][p-1];
			maxpos[i][p] = maxpos[i][p-1];
			if (j >= 0 && max[j][p-1] >= max[i][p-1]) {
				maxpos[i][p] = maxpos[j][p-1];
				max[i][p] = max[j][p-1];
			}
		}
 
		// Hinta alusta tähän on vähintään sama kuin aiemmin.
		hinta_alusta[i] = hinta_alusta[i-1];
 
		// Jos luku on alle minimitason, sen kasvatus maksaa.
		if (luku[i] < minimitaso[i-1]) {
			minimitaso[i] = minimitaso[i-1];
			hinta_alusta[i] += minimitaso[i] - luku[i];
		} else {
			minimitaso[i] = luku[i];
		}
	}
 
	// Lopusta alkuun.
	std::map<int, int> luvut;
	for (int i = n; i > 0; --i) {
		// Hinta tästä loppuun on vähintään sama kuin tätä seuraavasta.
		hinta_loppuun[i] = hinta_loppuun[i+1];
		luvut[luku[i]] += 1;
 
		// Kaikki liian pienet luvut pitää nostaa nykyiseen lukuun asti.
		while (luvut.begin()->first < luku[i]) {
			int pieni_luku = luvut.begin()->first, montako = luvut.begin()->second;
			luvut.erase(luvut.begin());
			luvut[luku[i]] += montako;
			hinta_loppuun[i] += montako * (long) (luku[i] - pieni_luku);
		}
	}
 
	for (int i = 0; i < q; ++i) {
		int a, b;
		std::cin >> a >> b;
 
		// Haetaan maksimin paikka.
		int c = max_valilla(a, b+1).second;
		// Alkupuolen hinta saadaan loppuhintojen erona.
		long ac = hinta_loppuun[a] - hinta_loppuun[c];
		// Loppupuolen hinta saadaan alkuhintojen erona, ja lisäksi pitää huomioida, että minimitaso voi olla eri kuin nyt löydetty huippu.
		long cb = hinta_alusta[b] - hinta_alusta[c] + (b - c) * (long) (luku[c] - minimitaso[c]);
		std::cout << (ac + cb) << '\n';
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED