Sto provando a risolvere muraglia tramite un segment tree dei massimi, ma ottengo output non corretto per i casi 2,3,4,9,15,16. L’implementazione della funzione chiedi è la seguente:
pair<int, int> chiedi(int x) {
pair<int, int> answer = {0, towers - 1};
int index = x + half_size, value = tree[index];
int i = 1, h = 1;
if (x != 0) {
while (i < half_size) {
if (value >= tree[i]) break;
if (i == (index >> (height - h))) {
i = index >> (height - (++h));
} else {
i <<= 1;
i++;
h++;
}
while (i > (1 << (h - 1)) && value >= tree[i]) i--;
}
if (i >= half_size) answer.first = i - half_size;
}
i = 1, h = 1;
if (x != towers - i) {
while (i < half_size) {
if (value >= tree[i]) break;
if (i == (index >> (height - h)))
i = index >> (height - (++h));
else {
i <<= 1;
h++;
}
while (i < ((1 << h) - 1) && value >= tree[i]) i++;
}
if (i >= half_size) answer.second = i - half_size;
}
return answer;
}
dove towers = N, height = ceil(log_2(N)) + 1, half_size = 1 << (height - 1).
Per gli input a cui ho accesso ottengo risultati corretti, non so cosa potrebbe non funzionare. Qualcuno può darmi una mano? Grazie