Zadanie Tetris 3D z OI C++ - złe wyniki

Witam, mam problem z zadaniem Tetris 3D z XIII OI - http://main.edu.pl/pl/archive/oi/13/tet , próbowałem sam to zrobić przed przeczytaniem wzorowego rozwiązania z książeczki. Większość testów jest wykonywana bezbłędnie (w niektórych na mainie zwraca mi program wywłaszczony), ale są 3 testy w jakich mam zły wynik (testy: tet3d, tet4d, tet13b) - są to duże testy i sam sobie nie poradzę, algorytm według jakiego działa program moim zdaniem nie wydaje się być zły, ale zastanawia mnie dlaczego te wyniki są nie takie jak powinny.
Schemat programu wygląda następująco - tworzone jest drzewo na wskaźnikach, następnie dla każdego klocka wyszukiwany jest najwyższy punkt, który potem zwiększam o wysokość danego klocka, potem aktualizuję tą wysokość na całym obszarze na jaki spada klocek.

 
#include <cstdio>
using namespace std;

// x, y - początek wieżchołka
// d_x, d_y długości klocków
// wielk - wielkość jaką będziemy uzupełniać
short x, y, d_x, d_y;
int wielk;

// struktura drzewa 
// ilosc - przechowuje jaka na danym węźle została zaktualiziwana wysokość
// ilosc_max - jaka wysokość jest masymalna w danym przedziale dla jakiego jest węzeł
// wskaźniki xy - prowadzą do przedziału dla pierwszej połowy z zakresu X i zakresy Y
// tam gdzie większa litera to przedział dla tej zmiennej będzie w większej połowie
// konstruktor odpowiednio zeruje zmienne na 0
struct ss {
	int ilosc;
	int ilosc_max;
	ss *xy, *xY, *Xy, *XY;
	ss() {
		ilosc_max = 0;
		ilosc = 0;
	}
};
// zwraca większą liczbę
int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

// uzupełnienie na dodawaniu rozgałęzień o mniejszym przedziale pól
void uzupelnij(ss *pocz, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// tu się nie rozgalezia, bo pole elementarne 1x1
	if (pocz_x == kon_x - 1 && pocz_y == kon_y - 1)
		return;

	else if (pocz_y == kon_y - 1) {
		// jak rozgalezia sia na OX bo Y ma szer 1
		int sr = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr, pocz_y, kon_y);
		uzupelnij((*pocz).Xy, sr, kon_x, pocz_y, kon_y);
	}

	else if (pocz_x == kon_x - 1) {
		// jak rozgalezia sia na OY bo X ma szer 1
		int sr = (pocz_y + kon_y) / 2;

		(*pocz).xy = new ss();
		(*pocz).xY = new ss();

		uzupelnij((*pocz).xy, pocz_x, kon_x, pocz_y, sr);
		uzupelnij((*pocz).xY, pocz_x, kon_x, sr, kon_y);
	}

	else {
		// jak rozgalezia sią na OX i OY
		int sr_y = (pocz_y + kon_y) / 2;
		int sr_x = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;
		(*pocz).xY = new ss;
		(*pocz).XY = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr_x, pocz_y, sr_y);
		uzupelnij((*pocz).xY, pocz_x, sr_x, sr_y, kon_y);
		uzupelnij((*pocz).Xy, sr_x, kon_x, pocz_y, sr_y);
		uzupelnij((*pocz).XY, sr_x, kon_x, sr_y, kon_y);
	}
}

// znalenienie maxa na danym przedziale polega na przeszukiwaniu
// tylko tych węzłów na których może znajdować się szukany fragment pola,
// na którym chcemy znaleźć maxa
// jak przedział cały zawiera się w polu to bierzemy ilosc_max - bo interesuje
// nas najwyższa wartość, natomiast jak tylko część to bieszemy ilosc,
// bo jeśli ta ilość jest najwyższa to nie znajdziemy jej w mniejszych przedziałach
int max_wysokosc(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y)
		return (*el).ilosc_max;

	// jak szukamy odpowiednich orzedziałów
	int sr_y = (pocz_y + kon_y) / 2;
	int sr_x = (pocz_x + kon_x) / 2;
	int max_wys = (*el).ilosc;

	// jak pierwszy x i y
	if 	(x < sr_x && y < sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).xy, pocz_x, sr_x, pocz_y, sr_y));

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& y < sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).Xy, sr_x, kon_x, pocz_y, sr_y));

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y - 1
		&& x < sr_x
		&& sr_y < y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).xY, pocz_x, sr_x, sr_y, kon_y));

	// jak drugi x i y
	if (pocz_y < kon_y - 1 && pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& sr_y < y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).XY, sr_x, kon_x, sr_y, kon_y));

	return max_wys;
}

// uzupełnienie obszaru daną wysokością polega na znaleznieniu (taką metodą jak we
// wcześniejszych funkcjach) obszaru który całkowicie podlega pod dany zakres na którym dodajemy
// na takim węźle uzupełniamy ilosc_max i ilosc bo obie te watrtści się zmienią
// na wyżaszch przesziałach dajemy w ilosc_max wyiększą wartość z pośród obecnej ilosci_max i wielkości jaką dodajemy
void uzupelnij_obszar_wielkoscia(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y) {
		(*el).ilosc = wielk;
		(*el).ilosc_max = wielk;
		return;
	}

	// ustalanie maksymalnej wielkości na weźle i obliczenie śr
	(*el).ilosc_max = max(wielk, (*el).ilosc_max);
	short sr_y = (pocz_y + kon_y) / 2;
	short sr_x = (pocz_x + kon_x) / 2;

	// jak pierwszy x i y
	if (x < sr_x && y < sr_y)
		uzupelnij_obszar_wielkoscia((*el).xy, pocz_x, sr_x, pocz_y, sr_y);

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& y < sr_y)
		uzupelnij_obszar_wielkoscia((*el).Xy, sr_x, kon_x, pocz_y, sr_y);

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y - 1
		&& x < sr_x
		&& sr_y < y + d_y)
		uzupelnij_obszar_wielkoscia((*el).xY, pocz_x, sr_x, sr_y, kon_y);

	// jak drugi x i y
	if (pocz_y < kon_y - 1 && pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& sr_y < y + d_y)
		uzupelnij_obszar_wielkoscia((*el).XY, sr_x, kon_x, sr_y, kon_y);
}

int main() {
	// wczytanie wiersza z głównymi danymi
	short X, Y, N;
	scanf("%hd%hd%hd", &X, &Y, &N);

	// utworzenie drzewa z korzeniem w pocz
	ss *pocz = new ss();
	uzupelnij(pocz, 0, X, 0, Y);

	// obsługa dodań kolejnych klocków
	int w; // wysokość klocka
	for (int a = 0; a < N; a++) {
		scanf("%hd%hd%d%hd%hd", &d_x, &d_y, &w, &x, &y);
		wielk = max_wysokosc(pocz, 0, X, 0, Y) + w;
		uzupelnij_obszar_wielkoscia(pocz, 0, X, 0, Y);
	}

	// wyświetlenie wyniku
	printf("%d", (*pocz).ilosc_max);

 	return 0;
}

Jeżeli coś źle napisałem to przypadkowo, sam uczę się algorytmiki, C++ też i pewnie mój kod nie jest idealny, ale bardzo proszę o pomoc :)

No dobra, ale czy widzi ktoś błąd w tym drzewie czwórkowym?

Nie wiem jak ci to powiedzieć, od ciebie spodziewano się czegoś w stylu: http://ideone.com/raLvIw

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef vector<unsigned> row;

int main()
  {
   unsigned W,H,N;
   cin>>W>>H>>N;
   vector<row> tb(H,row(W));
   while(N--)
     {
      unsigned w,h,z,sx,sy,zmax=0;
      cin>>w>>h>>z>>sx>>sy;
      w+=sx;
      h+=sy;
      for(unsigned y=sy;y<h;++y) for(unsigned x=sx;x<w;++x) zmax=max(zmax,tb[y][x]);
      zmax+=z;
      for(unsigned y=sy;y<h;++y) for(unsigned x=sx;x<w;++x) tb[y][x]=zmax;
     }
   unsigned zmax=0;  
   for(unsigned y=0;y<H;++y) for(unsigned x=0;x<W;++x) zmax=max(zmax,tb[y][x]);
   cout<<zmax<<endl;
   return 0;
  }

Natomiast to co stworzyłeś, to jakiś potwór GMO który nie ma prawa żyć.

markowanga napisał(a):

No dobra, ale czy widzi ktoś błąd w tym drzewie czwórkowym?

Spróbuj ten przykład:

10 10 2
10 10 1 1 5
1 1 5 5 5

Na moje oko źle porównujesz krawędzie przy ustawianiu maksimum.

Dobra :P Dalej nie wiem gdzie jest błąd, ale postanowiłem, sobie w wolnej chwili ten kod uprościć, w taki sposób, że przedziałami elementarnymi nie są współrzędne początku i końca a sam nr odcinka od początku (początek == koniec dla współrzędnych X i Y) pozamieniałem warunki w funkcjach i chodzi :D (no za wolne jest nadal niestety), umieszczam kod jakby komuś się przydał xD

#include <cstdio>
using namespace std;

// x, y - początek wieżchołka
// d_x, d_y długości klocków
// wielk - wielkość jaką będziemy uzupełniać
// wielkości te są odpowiednio zwiększane żeby poupraszczać 
// zakresy w przedziałach -> tak zajmujemy się numerami konkretneych odcinków,
// a nie współrzędnymi (współrzędne początku zwiększamy o 1 a długości skracamy o 1)
short x, y, d_x, d_y;
int wielk;

// struktura drzewa 
// ilosc - przechowuje jaka na danym węźle została zaktualiziwana wysokość
// ilosc_max - jaka wysokość jest masymalna w danym przedziale dla jakiego jest węzeł
// wskaźniki xy - prowadzą do przedziału dla pierwszej połowy z zakresu X i zakresy Y
// tam gdzie większa litera to przedział dla tej zmiennej będzie w większej połowie
// konstruktor odpowiednio zeruje zmienne na 0
struct ss {
	int ilosc;
	int ilosc_max;
	ss *xy, *xY, *Xy, *XY;
	ss() {
		ilosc_max = 0;
		ilosc = 0;
	}
};
// zwraca większą liczbę
int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

// uzupełnienie na dodawaniu rozgałęzień o mniejszym przedziale pól
void uzupelnij(ss *pocz, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// tu się nie rozgalezia, bo pole elementarne 1x1
	if (pocz_x == kon_x && pocz_y == kon_y)
		return;

	else if (pocz_y == kon_y) {
		// jak rozgalezia sia na OX bo Y ma szer 1
		int sr = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr, pocz_y, kon_y);
		uzupelnij((*pocz).Xy, sr + 1, kon_x, pocz_y, kon_y);
	}

	else if (pocz_x == kon_x) {
		// jak rozgalezia sia na OY bo X ma szer 1
		int sr = (pocz_y + kon_y) / 2;

		(*pocz).xy = new ss();
		(*pocz).xY = new ss();

		uzupelnij((*pocz).xy, pocz_x, kon_x, pocz_y, sr);
		uzupelnij((*pocz).xY, pocz_x, kon_x, sr + 1, kon_y);
	}

	else {
		// jak rozgalezia sią na OX i OY
		int sr_y = (pocz_y + kon_y) / 2;
		int sr_x = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;
		(*pocz).xY = new ss;
		(*pocz).XY = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr_x, pocz_y, sr_y);
		uzupelnij((*pocz).xY, pocz_x, sr_x, sr_y + 1, kon_y);
		uzupelnij((*pocz).Xy, sr_x + 1, kon_x, pocz_y, sr_y);
		uzupelnij((*pocz).XY, sr_x + 1, kon_x, sr_y + 1, kon_y);
	}
}

// znalenienie maxa na danym przedziale polega na przeszukiwaniu
// tylko tych węzłów na których może znajdować się szukany fragment pola,
// na którym chcemy znaleźć maxa
// jak przedział cały zawiera się w polu to bierzemy ilosc_max - bo interesuje
// nas najwyższa wartość, natomiast jak tylko część to bieszemy ilosc,
// bo jeśli ta ilość jest najwyższa to nie znajdziemy jej w mniejszych przedziałach
int max_wysokosc(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y)
		return (*el).ilosc_max;

	// jak szukamy odpowiednich orzedziałów
	int sr_y = (pocz_y + kon_y) / 2;
	int sr_x = (pocz_x + kon_x) / 2;
	int max_wys = (*el).ilosc;

	// jak pierwszy x i y
	if 	(x <= sr_x && y <= sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).xy, pocz_x, sr_x, pocz_y, sr_y));

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x // teraz wiem, że istnieje drugi x
		&& sr_x + 1 <= x + d_x
		&& y <= sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).Xy, sr_x + 1, kon_x, pocz_y, sr_y));

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y
		&& x <= sr_x
		&& sr_y + 1 <= y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).xY, pocz_x, sr_x, sr_y + 1, kon_y));

	// jak drugi x i y
	if (pocz_y < kon_y && pocz_x < kon_x
		&& sr_x + 1 <= x + d_x
		&& sr_y + 1 <= y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).XY, sr_x + 1, kon_x, sr_y + 1, kon_y));

	return max_wys;
}

// uzupełnienie obszaru daną wysokością polega na znaleznieniu (taką metodą jak we
// wcześniejszych funkcjach) obszaru który całkowicie podlega pod dany zakres na którym dodajemy
// na takim węźle uzupełniamy ilosc_max i ilosc bo obie te watrtści się zmienią
// na wyżaszch przesziałach dajemy w ilosc_max wyiększą wartość z pośród obecnej ilosci_max i wielkości jaką dodajemy
void uzupelnij_obszar_wielkoscia(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y) {
		(*el).ilosc = wielk;
		(*el).ilosc_max = wielk;
		return;
	}

	// ustalanie maksymalnej wielkości na weźle i obliczenie śr
	(*el).ilosc_max = max(wielk, (*el).ilosc_max);
	short sr_y = (pocz_y + kon_y) / 2;
	short sr_x = (pocz_x + kon_x) / 2;

	// jak pierwszy x i y
	if (x <= sr_x && y <= sr_y)
		uzupelnij_obszar_wielkoscia((*el).xy, pocz_x, sr_x, pocz_y, sr_y);

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x // teraz wiem, że istnieje drugi x
		&& sr_x + 1 <= x + d_x
		&& y <= sr_y)
		uzupelnij_obszar_wielkoscia((*el).Xy, sr_x + 1, kon_x, pocz_y, sr_y);

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y
		&& x <= sr_x
		&& sr_y + 1 <= y + d_y)
		uzupelnij_obszar_wielkoscia((*el).xY, pocz_x, sr_x, sr_y + 1, kon_y);

	// jak drugi x i y
	if (pocz_y < kon_y && pocz_x < kon_x
		&& sr_x + 1 <= x + d_x
		&& sr_y + 1 <= y + d_y)
		uzupelnij_obszar_wielkoscia((*el).XY, sr_x + 1, kon_x, sr_y + 1, kon_y);
}

int main() {
	// wczytanie wiersza z głównymi danymi
	short X, Y, N;
	scanf("%hd%hd%hd", &X, &Y, &N);

	// utworzenie drzewa z korzeniem w pocz
	ss *pocz = new ss();
	//uzupelnij(pocz, 0, X, 0, Y);
	uzupelnij(pocz, 1, X, 1, Y);

	// obsługa dodań kolejnych klocków
	int w; // wysokość klocka
	for (int a = 0; a < N; a++) {
		scanf("%hd%hd%d%hd%hd", &d_x, &d_y, &w, &x, &y);
		x++;
		y++;
		d_x--;
		d_y--;
		wielk = max_wysokosc(pocz, 1, X, 1, Y) + w;
		uzupelnij_obszar_wielkoscia(pocz, 1, X, 1, Y);
	}

	// wyświetlenie wyniku
	printf("%d", (*pocz).ilosc_max);

 	return 0;
}

Nie czytałem Twojego rozwiązania.
Jednak samemu zrobiłem je stosując drzewo przedziałowe gdzie w węzłach trzymałem drzewo przedziałowe (incepcja :P).

Jak chcesz o testować czy dobrze napisałeś "pojedyncze" drzewo polecam zadanie "http://main.edu.pl/pl/user.phtml?op=showtask&task=tet&con=ALG". Tylko haczyk jest taki, że w tym zadaniu napisz te drzewo w ładnej klasie.

Tak jak napisał @withelm najpierw musisz nauczyć się klepać drzewo przedziałowe i to przedział - przedział, czyli wykonujesz coś na przedziale i pytasz o przedział. W tym przypadku to chyba będzie drzewo(max, max). Jeśli chcesz podobne zadanie gdzie wystarczy jedno drzewo a nie drzewo drzew to Koleje z OIa.

Co do materiałów: http://was.zaa.mimuw.edu.pl/?q=node/8 no i niebieskie książeczki :3

Te dodatkowe zmienne to int i bool. int odpowiada za max wartości na tym przedziale, a bool to jest informacja czy dany przedział jest wypełniony tym maksem.

Gdy wprowadzasz przedział to sprawdzasz czy ten podprzedział pokrywa się z podprzedziałem (drzew) jak tak to już nie wchodzisz głębiej w drzewo a ustalasz bool na true.
Gdy jednak musisz wejść głębiej a dany podprzedział ma flagę true to:

1. kopiujesz int'a i boola z przedziału <a,b> na <a1, b1>, <a2, b2>.
2. usuwasz true z przedział <a,b>
3. Idziesz rekurencją niżej.
   Przy powrocie ustalasz <a,b> = max(<a1,b1>, <a2,b2>)

Gdy masz odczytać maksimum z przedziału robisz dokładnie to samo rozbijasz <a,b> na małe podprzedziały <a1,b1> <a2,b2> itd i wyciągasz maksa. Pamiętaj tylko aby sprawdzać boola czy nie oznacza całego przedziału. W takim przypadku nie wchodzisz głębiej

Najłatwiej takie drzewo napisać rekurencyjnie. Funkcje do wprowadzenia i odczytu z przedziału są bardzo podobne do siebie