W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Tym razem Bajtocja ma kształt prostokąta o wymiarach na metrów. Bajtazar jest farmerem i ma swoje pole uprawne, składające się z obszarów jednostkowych. Ponadto część wspólna każdej poziomej warstwy obszarów jednostkowych z polem Bajtazara jest spójna (samo pole jednakże nie musi być spójne).
Król Bajtocji wydał dekret, na mocy którego z każdego pola uprawnego należy oddać królowi prostokątny obszar o wymiarach na metrów, złożony wyłącznie z całych obszarów jednostkowych. Jego położenie wybiera sam król. Jedyną nadzieją farmera Bajtazara jest to, że istnieje bardzo dużo możliwych takich położeń i być może zachłannemu królowi nie uda się zbyt szybko podjąć decyzji o wyborze położenia. Pomóż Bajtazarowi i policz, ile jest możliwych położeń takiego obszaru na polu Bajtazara?
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite , , i (), oznaczające odpowiednio wymiary Bajtocji oraz wymiary prostokątnego obszaru, który ma być oddany królowi. Kolejnych wierszy zawiera opisy kolejnych poziomych warstw pola Bajtazara. Każdy z nich składa się z dwóch liczb całkowitych i (, , ) oznaczających, że fragment pola na tej warstwie zaczyna się metrów od lewego brzegu Bajtocji i składa się z obszarów jednostkowych.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę możliwych położeń prostokąta o wymiarach na na polu Bajtazara.
5 6 2 3 1 5 1 3 1 2 1 1 3 3 2 4poprawną odpowiedzią jest:
3
Powyższy rysunek przedstawia pole uprawne z przykładowego wejścia (powierzchnia należąca do pola została zamalowana na czarno).
Programujących w C++ zachęcamy do rozważnego korzystania z STL-owych struktur danych, ponieważ ze względu na rozmiar danych, ich używanie może spowodować przekroczenie limitu czasowego lub pamięciowego.
Autor zadania: Jakub Radoszewski.