Pole uprawne
Limit pamięci: 128 MB
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?
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis pola uprawnego farmera
i rozmiary prostokątnego obszaru, który ma być oddany królowi,
- obliczy liczbę możliwych położeń takiego obszaru na polu,
- wypisze wynik na standardowe wyjście.
Wejście
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.
Wyjście
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.
Przykład
Dla danych wejściowych:
5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4
poprawną odpowiedzią jest:
3
Powyższy rysunek przedstawia pole uprawne z przykładowego wejścia (powierzchnia należąca do pola została zamalowana na czarno).
Uwaga
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.