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: