URGENTE Grande Muraglia (muraglia) - TLE nonostante usi i segment tree

Ciao a tutti,
sto cercando di ottenere almeno il livello argento in tutti i “nodi” di algobadge per essere ammesso alle fasi nazionali ma non riesco a risolvere muraglia. In particolare il mio codice risolve correttamente le subtask 1 e 2 e qualche test case delle successive mentre per tutti gli altri mi dà TLE. Ho già cercato sul forum varie richieste di aiuto su questo problema e tutte indicavano che la soluzione è usare i segment tree (infatti io ne ho usato uno che immagazzina il massimo in un certo range). Inoltre ho cercato ulteriori informazioni su questo sito ma comunque non capisco come rendere la mia soluzione più efficiente. Qualcuno ha dei consigli?
Grazie mille!

#include <utility>
#include <vector>
using namespace std;

vector<int> muragliaMax, muraglia;
bool stop = false;

int maximum(int a, int b) {
	if (a > b) {
		return a;
	} else {
		return b;
	}
}

int minimum(int a, int b) {
	if (a > b) {
		return b;
	} else {
		return a;
	}
}

int average(int a, int b) {
	return (a + b) / 2;
}

// inizializza il segment tree
void create(int start, int finish, vector<int> v, int index) {
	if (finish != start) {
		int av = average(finish, start);
		create(av + 1, finish, v, 1 + index * 2);
		create(start, av, v, index * 2);
		muragliaMax[index] = max(muragliaMax[1 + index * 2], muragliaMax[index * 2]);
	} else {
		muragliaMax[index] = v[finish];
	}
}

//aggiorna il segment tree con il valore newVal alla posizione nel 
//segment tree  corrispondente a newPosition nel vettore di partenza
void aggiorna(int newVal, int newPosition, int k, int intStart, int intFinish) {
	if (intFinish == intStart) {
		muragliaMax[k] = newVal;
	} else {
		int av = average(intStart, intFinish);
		if (av < newPosition) {
			aggiorna(newVal, newPosition, k * 2 + 1, av + 1, intFinish);
		} else {
			aggiorna(newVal, newPosition, k * 2, intStart, av);
		}
		muragliaMax[k] = max(muragliaMax[k * 2 + 1], muragliaMax[k * 2]);
	}
}

//trova l'indice dell'elemento maggiore o uguale di than nell'intervallo da ansStart ad
//ansFinish. In caso ce ne siano più di uno, restituisce quello con indice maggiore
int largestLarger(int than, int intStart, int intFinish, int ansStart, int ansFinish, int k) {
	if (intStart > ansFinish || muragliaMax[k] < than || intFinish < ansStart) {
		return 0;
	} else if (intFinish == intStart){
		return intStart;
	} else {
		int av = average(intStart, intFinish), newll = largestLarger(than, av + 1, intFinish, ansStart, ansFinish, k * 2 + 1);
		if (newll != 0) {
			return newll;
		} else {
			return largestLarger(than, intStart, av, ansStart, ansFinish, k * 2);
		}
	}
}

//trova l'indice dell'elemento maggiore o uguale di than nell'intervallo da ansStart ad
//ansFinish. In caso ce ne siano più di uno, restituisce quello con indice minore
int smallestLarger(int than, int intStart, int intFinish, int ansStart, int ansFinish, int k) {
	if (intStart > ansFinish || muragliaMax[k] < than || intFinish < ansStart) {
		return 0;
	} else if (intFinish == intStart){
		return intStart;
	} else {
		int av = average(intStart, intFinish), newll = smallestLarger(than, intStart, av, ansStart, ansFinish, k * 2);
		if (newll != 0) {
			return newll;
		} else {
			return smallestLarger(than, av + 1, intFinish, ansStart, ansFinish, k * 2 + 1);
		}
	}
}

pair<int, int> chiedi(int x) {
    int ls = maximum(x - 1, 0), sl = minimum(x + 1, muraglia.size() - 1);
	ls = largestLarger(muraglia[x] + 1, 0, muraglia.size() - 1, 0, ls, 1);
	sl = smallestLarger(muraglia[x] + 1, 0, muraglia.size() - 1, sl, muraglia.size() - 1, 1);
	if (ls >= x) {
		ls = 0;
	}
	if (sl <= x) {
		sl = muraglia.size() - 1;
	}
    return {ls, sl};
}

void cambia(int x, int h) {
	muraglia[x] = h;
	aggiorna(h, x, 1, 0, muraglia.size() - 1);
	return;
}

void inizializza(int N, vector<int> H) {
	muragliaMax.resize(4 * N);
	muraglia.resize(N);
	create(0, N - 1, H, 1);
	for (int i = 0; i < N; i++) {
		muraglia[i] = H[i];
	}
	return;
}


Il tuo codice senza le funzioni maximum(), minimum(), average() e con qualche altra accortezza fa tranquillamente 100.

Grazie mille! Non capisco comunque come ottimizzare la soluzione oltre a togliere quelle funzioni, riusciresti a darmi qualche altro consiglio?

Le funzioni largestLarger e smallestLarger hanno una complessità logaritmica, ma usando anche la ricerca binaria (complessità logaritmica) la complessità totale diventa log²N. Per evitare TLE hai bisogno di un algoritmo con complessità log N.