Muraglia (Execution killed (could be triggered by violating memory limits))

Sto risolvendo muraglia con un segment tree, ma mi uccide l’esecuzioni in tutti i task tranne il secondo.
se lo eseguo in locale mi fa anche il primo esempio, occupa veramente troppa memoria?

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

int grandezza;
int levels=0;
int padding=0;
int a[]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1000001};
int Z[2000000]={0};

int destra(int x){
	if(x==grandezza-1){
		return grandezza-1;
	}
	int value=Z[padding+x];
	int temppad=padding;
	int indice=padding+x;
	int templev=levels;
	while(templev>=0){
		if(value<Z[indice+1]){
			indice++;
			break;
		}
		indice=(indice/2)-1;
		if(indice==(temppad-1)){
			return grandezza-1;
		}
		temppad=temppad-a[templev];
		templev--;
	}
	if(templev==-1){
		return grandezza-1;
	}
	while(templev<levels){
		indice=(indice*2)+2;
		if(Z[indice]<=value){
			indice++;
		}
		templev++;
	}
	return indice-padding;
}

int sinistra(int x){
	if(x==0){
		return 0;
	}
	int value=Z[padding+x];
	int temppad=padding;
	int indice=padding+x;
	int templev=levels;
	while(templev>=0){
		if(value<Z[indice-1]){
			indice--;
			break;
		}
		indice=(indice/2)-1;
		temppad=temppad-a[templev];
		if(indice==temppad){
			return 0;
		}
		templev--;
	}
	if(templev==-1){
		return 0;
	}
	while(templev<levels){
		indice=(indice*2)+3;
		if(Z[indice]<=value){
			indice--;
		}
		templev++;
	}
	return indice-padding;
}

pair<int, int> chiedi(int x) {
    return {sinistra(x), destra(x)};
}

void cambia(int x, int h) {
	int old=Z[padding+x];
	Z[padding+x]=h;
		int temppad=padding;
		int templev=levels;
		int z=x;
		if(z%2==1){
			z--;
		}
		while(templev>0){
			int dest=((temppad+z)/2)-1;
			if(Z[padding+z]>Z[temppad+z+1]){
				Z[dest]=Z[temppad+z];
			}else{
				Z[dest]=Z[temppad+z+1];
			}
			temppad=temppad-a[templev];
			templev--;
		}
    return;
}

void inizializza(int N, vector<int> H) {
	grandezza=N;
	while(a[levels]<N){
		padding=padding+a[levels];
		levels++;
	}
	for(int i=0;i<N;i++){
		Z[i+padding]=H[i];
	}
	int temppad=padding;
	int templev=levels;
	while(templev>=0){
		int z=0;
		while(z<a[templev]){
			int dest=((temppad+z)/2)-1;
			if(Z[temppad+z]>Z[temppad+z+1]){
				Z[dest]=Z[temppad+z];
			}else{
				Z[dest]=Z[temppad+z+1];
			}
			z=z+2;			
		}
		templev--;
		temppad=temppad-a[templev];
	}
	return;
}

Dopo qualche modifica al codice sono riuscito a fargli fare la prima subtask ma mi da output incorretto(nelle altre subtask continua a dare execution killed),onestamente non so dove mettere le mani

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

int grandezza;
int levels=0;
int padding=0;
int a[22]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1000001};
int Z[2000000]={0};

int destra(int x){
	if(x==grandezza-1){
		return grandezza-1;
	}
	int value=Z[padding+x];
	int temppad=padding;
	int indice=padding+x;
	int templev=levels;
	while(templev>=0){
		if(value<Z[indice+1]){
			indice++;
			break;
		}
		indice=(indice/2)-1;
		if(indice==(temppad-1)){
			return grandezza-1;
		}
		templev--;
		temppad=temppad-a[templev];
	}
	if(templev==-1){
		return grandezza-1;
	}
	while(templev<levels){
		indice=(indice*2)+2;
		if(Z[indice]<=value){
			indice++;
		}
		templev++;
	}
	return indice-padding;
}

int sinistra(int x){
	if(x==0){
		return 0;
	}
	int value=Z[padding+x];
	int temppad=padding;
	int indice=padding+x;
	int templev=levels;
	while(templev>=0){
		if(value<Z[indice-1]){
			indice--;
			break;
		}
		indice=(indice/2)-1;
		templev--;
		temppad=temppad-a[templev];
		if(indice==temppad){
			return 0;
		}
	}
	if(templev==-1){
		return 0;
	}
	while(templev<levels){
		indice=(indice*2)+3;
		if(Z[indice]<=value){
			indice--;
		}
		templev++;
	}
	return indice-padding;
}

pair<int, int> chiedi(int x) {
    return {sinistra(x), destra(x)};
}

void cambia(int x, int h) {
	int old=Z[padding+x];
	Z[padding+x]=h;
		int temppad=padding;
		int templev=levels;
		int z=x;
		if(z%2==1){
			z--;
		}
		while(templev>=0){
			int dest=((temppad+z)/2)-1;
			if(Z[padding+z]>Z[temppad+z+1]){
				Z[dest]=Z[temppad+z];
			}else{
				Z[dest]=Z[temppad+z+1];
			}
			templev--;
			temppad=temppad-a[templev];
		}
    return;
}

void inizializza(int N, vector<int> H) {
	grandezza=N;
	while(a[levels]<N){
		padding=padding+a[levels];
		levels++;
	}
	for(int i=0;i<N;i++){
		Z[i+padding]=H[i];
	}
	int temppad=padding;
	int templev=levels;
	while(templev>0){
		int z=0;
		while(z<a[templev]){
			int dest=((temppad+z)/2)-1;
			if(Z[temppad+z]>Z[temppad+z+1]){
				Z[dest]=Z[temppad+z];
			}else{
				Z[dest]=Z[temppad+z+1];
			}
			z=z+2;			
		}
		templev--;
		temppad=temppad-a[templev];
	}
	return;
}

Ciao, l’errore di memoria è dovuto al fatto che anche l’ultimo valore dell’array a dev’essere una potenza di 2 e ne devi tenere conto anche nel dimensionare il segment tree Z che deve risultare 2*a[].
Questa semplice correzione risolve solo il subtask 4 dove la funzione cambia() non viene mai utilizzata.
Con il seguente input:

14 4
27 4 3 2 6 4 1 9 10 7 19 15 8 31
S 7 1
Q 7
S 8 1
Q 8

l’algoritmo sbaglia l’ulima query.

sono riuscito a risolvere l’errore di memoria ora rivedo l’algoritmo

ti ringrazio, dopo i tuoi consigli sono riuscito a fare 100/100