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