Sto provando a scrivere la funzione “valuta” del problema skyline con una Range Maximum Query con sparse table, ma supera i limiti di memoria (non di tempo).
Ho provato a usare sia array/matrici, sia vettori dinamici (nella parte commentata).
Per risolvere il problema pensavo a un modo per evitare di copiare il vettore di partenza in globale, ma in teoria non dovrei risparmiare così tanta memoria…
Forse devo provare con un altro metodo?
Ciao, purtroppo penso che non si possa usare un approccio con sparse table in quanto con N \le 10^6, devi memorizzare fino a Nlog(N) = 10^6 \times 20 = 2 \times 10^7 interi.
Siccome ti servono interi a 32 bit, l’utilizzo di memoria sarà circa 4 \times 2 \times 10^7 \approx 80 MiB, che i supera 64 MiB concessi per risolvere il problema.
PS: Cerca di ragionare sul tipo di RMQ a cui ti serve rispondere, è davvero necessaria una struttura dati per calcolare ogni possibile RMQ?
Comunque, puoi modificare la Sparse Table per costruirla (ad esempio) usando metà della memoria (controllando però il doppio di intervalli per ogni query).
Anche se tipicamente non è un’idea particolarmente utile