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

**URL:** <https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908>\
**Category:** Aiuto\
**Created:** [20 Giugno 2024, 8:21am UTC](https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908 "2024-06-20T08:21:58Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![FraGhila](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/e79b87/32.png) [@FraGhila](https://forum.olinfo.it/u/FraGhila)\
**Post date:** [20 Giugno 2024, 8:21am UTC](https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908/1 "2024-06-20T08:21:58Z")

</div>

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](https://cp-algorithms.com/data_structures/segment_tree.html) ma comunque non capisco come rendere la mia soluzione più efficiente. Qualcuno ha dei consigli?  
Grazie mille!

```C++
#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;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [20 Giugno 2024, 9:32am UTC](https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908/2 "2024-06-20T09:32:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![FraGhila](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/e79b87/32.png) [@FraGhila](https://forum.olinfo.it/u/FraGhila)\
**Post date:** [20 Giugno 2024, 9:55am UTC](https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908/3 "2024-06-20T09:55:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![vincenzorende](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vincenzorende/32/1809_2.png) [@vincenzorende](https://forum.olinfo.it/u/vincenzorende)\
**Post date:** [21 Giugno 2024, 2:44pm UTC](https://forum.olinfo.it/t/urgente-grande-muraglia-muraglia-tle-nonostante-usi-i-segment-tree/8908/4 "2024-06-21T14:44:33Z")

</div>

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.