# Skyline 72% (sparse table) **URL:** \ **Category:** Aiuto\ **Created:** [2 Giugno 2018, 1:17pm UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234 "2018-06-02T13:17:11Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![madeve](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/90db22/32.png) [@madeve](https://forum.olinfo.it/u/madeve)\ **Post date:** [2 Giugno 2018, 1:17pm UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/1 "2018-06-02T13:17:11Z")
Sto provando a scrivere la funzione “valuta” del problema [skyline](https://training.olinfo.it/#/task/skyline/statement) con una Range Maximum Query con sparse table, ma supera i limiti di memoria (non di tempo). [https://pastebin.com/t0bTJKyW](https://pastebin.com/t0bTJKyW) 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? ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [3 Giugno 2018, 8:21am UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/2 "2018-06-03T08:21:26Z")
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? 🙂 ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [4 Giugno 2018, 7:51am UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/3 "2018-06-04T07:51:41Z")
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 🙂 ---
**Author:** ![madeve](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/90db22/32.png) [@madeve](https://forum.olinfo.it/u/madeve)\ **Post date:** [4 Giugno 2018, 11:27am UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/4 "2018-06-04T11:27:51Z")
Se ho capito bene, l’idea migliore sarebbe usare un segment tree? ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [4 Giugno 2018, 12:47pm UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/5 "2018-06-04T12:47:36Z")
No, usare un segment tree dovrebbe prendere punteggio pieno ma non è l’idea migliore 🙂 Le RMQ che devi calcolare sono tutte del tipo (0, i) o (i, N-1). Il primo tipo sono prefissi e il secondo tipo suffissi, riesci a calcolarli in O(N) ? ---
**Author:** ![madeve](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/90db22/32.png) [@madeve](https://forum.olinfo.it/u/madeve)\ **Post date:** [4 Giugno 2018, 5:13pm UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/6 "2018-06-04T17:13:57Z")
Ok, ho fatto 100% memorizzando tutti i prefissi e i suffissi in due array separati: [https://pastebin.com/7m0NrvDb](https://pastebin.com/7m0NrvDb) Intendevi una cosa del genere, vero? Grazie mille ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [4 Giugno 2018, 8:47pm UTC](https://forum.olinfo.it/t/skyline-72-sparse-table/5234/7 "2018-06-04T20:47:36Z")
Direi proprio di sì, ottimo 😉