Szczegółowe omówienie zadania Tetris 2D:

Link do powyższego omówienia zadania Tetris 2D:
https://youtu.be/w9hcR2ZYsPc?t=987

Link do treści zadania Tetris 2D oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/-0A1PC3fNc2RK-qvoUQKGGLl/site

–
Zadanie Tetris 2D jest szkoleniowym zadaniem pokazującym drzewa przedział-przedział:
https://youtu.be/hHNjFBxNO54?t=2197
Drzewa przedziałowe to sumy prefiksowe z mała obserwacją:
https://youtu.be/hHNjFBxNO54?t=2159
Wszystko jesteśmy w stanie udoskonalić:
https://youtu.be/hHNjFBxNO54?t=29

–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

–
Kod C++ programu Tetris 2D, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;
const int MAX_ROZMIAR_DRZEWA = 1<<21;
int drzewo_max[MAX_ROZMIAR_DRZEWA];
int na_pozniej[MAX_ROZMIAR_DRZEWA];
int ZnajdzNajblizszaWiekszaPotegeDwojki (int liczba) {
int najblizsza_potega_dwojki;
najblizsza_potega_dwojki = 1;
while (najblizsza_potega_dwojki < liczba)
najblizsza_potega_dwojki <<= 1;
return najblizsza_potega_dwojki;
}
void ZaktualizujSynow (int v) {
if (na_pozniej[v] == 0)
return;
drzewo_max[2*v] = na_pozniej[v];
drzewo_max[2*v + 1] = na_pozniej[v];
na_pozniej[2*v] = na_pozniej[v];
na_pozniej[2*v + 1] = na_pozniej[v];
na_pozniej[v] = 0;
}
int ObliczMaksNaPrzedziale (int p, int k, int v, int a, int b) {
int maks_syna_lewego;
int maks_syna_prawego;
//pytanie poza przedziaem wierzchoka
if ( (a > k) || (b < p) )
return 0;
//wierzchoek cakowicie w pytanym przedziale
if ( (a >= p) && (b <= k) )
return drzewo_max[v];
//wierzchoek czesciowo w pytanym przedziale
ZaktualizujSynow (v);
maks_syna_lewego = ObliczMaksNaPrzedziale(p, k, 2*v, a, (a + b)/2);
maks_syna_prawego = ObliczMaksNaPrzedziale(p, k, 2 * v + 1, (a + b)/2+1, b);
return max(maks_syna_lewego, maks_syna_prawego);
}
void UstawMaksNaPrzedziale (int p, int k, int v, int a, int b, int wartosc) {
//pytanie poza przedziaem wierzchoka
if ( (a > k) || (b < p) )
return;
//wierzchoek cakowicie w pytanym przedziale
if ( (a >= p) && (b <= k) ) {
drzewo_max[v] = wartosc;
na_pozniej[v] = wartosc;
return;
}
//wierzchoek czesciowo w pytanym przedziale
ZaktualizujSynow (v);
UstawMaksNaPrzedziale(p, k, 2*v, a, (a + b) / 2, wartosc);
UstawMaksNaPrzedziale(p, k, 2*v + 1, (a + b) / 2 + 1, b, wartosc);
drzewo_max[v] = max(drzewo_max[2*v], drzewo_max[2*v + 1]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int liczba_klockow, rozmiar_planszy;
int liczba_przechowywanych_elementow, rozmiar_drzewa;
int max_na_przedziale;
int numer_poczatkowy_klocka, numer_koncowy_klocka, dlugosc_klocka;
int i;
cin >> rozmiar_planszy >> liczba_klockow;
liczba_przechowywanych_elementow = ZnajdzNajblizszaWiekszaPotegeDwojki (rozmiar_planszy);
rozmiar_drzewa = 2 * liczba_przechowywanych_elementow;
for (i = 0; i < liczba_klockow; i++) {
cin >> dlugosc_klocka >> numer_poczatkowy_klocka;
--dlugosc_klocka;
    numer_koncowy_klocka = numer_poczatkowy_klocka + dlugosc_klocka;
max_na_przedziale = ObliczMaksNaPrzedziale(numer_poczatkowy_klocka, numer_koncowy_klocka, 1, 0, liczba_przechowywanych_elementow-1);
UstawMaksNaPrzedziale(numer_poczatkowy_klocka, numer_koncowy_klocka, 1, 0, liczba_przechowywanych_elementow-1, max_na_przedziale + 1);	
}
cout << ObliczMaksNaPrzedziale(0, liczba_przechowywanych_elementow-1, 1, 0, liczba_przechowywanych_elementow-1) << "\n";
return 0;
}