Jak ograniczyc zuzycie pamieci?

// Przepraszam z gory za brak polskich znakow.

W zadaniu http://potyczki.mimuw.edu.pl/user.php/mal.pdf?op=get&id=88968 (uprzedzam, ze runda nadal trwa, wiec nie prosze o pomoc w rozwiazaniu), jest mowa o tym, ze najwyzsza wspolrzedna x i y sciany wynosi 10^{9, wiec max powierzchnia sciany to 10}18. Dla tablicy kilka milionow tera to niestety troche za duzo; dostepna pamiec to 128 MB.

Czego wiec uzyc, jezeli nie tablicy, do przechowania danych? Dynamiczna alokacja pamieci chyba bedzie tu na nic. Czy moze sie myle?

Nie żartuj że chcesz to robić takim naiwnym algorytmem żeby sobie oznaczać w tablicy ile razy jakiś kawałek ktoś pomalował... Ani życia ani pamięci ci na to nie starczy...
To nie jest kwestia "jak zmniejszyć zużycie pamięci" tylko kwestia totalnie błędnego algorytmu. Nie tędy droga.

Pierwszy z brzegu pomysł: zapisać tablicę współrzędnych zaś ścianę obrabiać fragmentami.

Co rozumiesz przez "obrabianie fragmentami"?

Dziel i zwyciężaj.

Chodzi o to, abyś najpierw wczytał wszystkie współrzędne i zapisał je sobie w jakiejś strukturze. Podzielił ścianę na części. Dla każdej części z osobna wybrał te elementy które na nią nachodzą i obliczył wynik (tylko dla tej części). Na końcu zsumował wyniki z wszystkich części.

Zwykła lista by wystarczyła, ale chcąc otrzymać lepsze czasy trzeba by skonstruować jakiś lepszy kontener (jakieś dwuwymiarowe drzewo przedziałowe) który przyspieszy operację wyboru elementów. Również pod hasłem "podzielił ścianę na części" kryje się pole do popisu. Szybkość algorytmu będzie zależeć od sposobu w jaki dokonujesz podziału.