Kyselyt

#include <bits/stdc++.h>

#define MAXPOW 19

int n, q;
int t[200002];
int lkm[200002][MAXPOW];
long sum[200002][MAXPOW];
int max[200002][MAXPOW];
int maxpos[200002][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]};
}

long summa(int a, int b) {
	int l = b - a;
	int pow = __builtin_ctz(l & -l);
	int p = a + (1 << pow);
	if (p == b) {
		return sum[p-1][pow];
	}
	return sum[p-1][pow] + summa(p, b);
}

std::unordered_map<long, long> cache;
long tulos(int a, int b) {
	long key = ((long)a << MAXPOW) + b;
	auto iter = cache.find(key);
	if (iter != cache.end()) {
		return iter->second;
	}

	auto m = max_valilla(a, b);
	if (t[a] == m.first) {
		return cache[key] = (b - a) * (long) m.first - summa(a, b);
	}
	int p = m.second;
	return cache[key] = tulos(a, p) + tulos(p, b);
}

int main() {
	std::cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		std::cin >> t[i];
		lkm[i][0] = 1;
		sum[i][0] = t[i];
		max[i][0] = t[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];
			lkm[i][p] = lkm[i][p-1];
			sum[i][p] = sum[i][p-1];
			maxpos[i][p] = maxpos[i][p-1];
			if (j >= 0) {
				if (max[j][p-1] >= max[i][p-1]) {
					maxpos[i][p] = maxpos[j][p-1];
					max[i][p] = max[j][p-1];
				}
				lkm[i][p] += lkm[j][p-1];
				sum[i][p] += sum[j][p-1];
			}
		}
	}
	for (int i = 0; i < q; ++i) {
		int a, b;
		std::cin >> a >> b;
		std::cout << tulos(a - 1, b) << '\n';
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 3

Verdict: ACCEPTED