Kyselyt

#include <iostream>
#include <algorithm>

#define MAXPOW 19

int n, q;
int t[200002];
int lkm[200002][MAXPOW];
int sum[200002][MAXPOW];
int max[200002][MAXPOW];

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) {
		return max[p-1][pow];
	}
	return std::max(max[p-1][pow], max_valilla(p, b));
}

int 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);
}

int tulos(int a, int b) {
	int m = max_valilla(a, b);
	if (t[a] == m) {
		return (b - a) * m - summa(a, b);
	}
	int p0 = a, p1 = b;
	while (p1 - p0 > 1) {
		int p = (p0 + p1) / 2;
		if (max_valilla(a, p) == m) {
			p1 = p;
		} else {
			p0 = p;
		}
	}
	return tulos(a, p0) + tulos(p0, 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];
		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];
			if (j >= 0) {
				max[i][p] = std::max(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: WRONG ANSWER