Runda 11 [Hard] - Żniwa

14.02.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 11; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 128MB

 


 

Żniwa

Jak co roku w dalekich krainach liczb pierwszych nadszedł czas żniw. Każdy rolnik planuje zebrać ze swojego pola owoc całorocznych prac - dorodne liczby nieujemne. Powierzchnię upraw można podzielić na małe poletka rozmiaru 1x1, każde rodzące w czasie upraw jedną liczbę nieujmną. Kiedy rolnik decyduje się na zbiór, wyznacza prostokąt składający się z sąsiadujących małych poletek i zbiera z niego plon - iloczyn liczb ze składających się nań poletek, modulo pewna liczba pierwsza.

Zostałeś wyznaczony do pomiaru plonu dla różnych możliwych scenariuszy zbioru. Otrzymałeś listę prostokątów, o które mogą pytać Cię rolnicy, a Twoim zadaniem jest odpowiedzieć im, jak duży plon zbiorą.

Wejście:

Pierwsza linia wejścia zawiera trzy liczby $ n $, $ m $ oraz $ p $ - odpowiednio wysokość i szerokość pola uprawnego oraz liczbę pierwszą, modulo którą należy podawać wyniki. ($ 1 \leq n,m \leq 1000, 2 \leq p \leq 10^{9} $) W kolejnych $ n $ liniach dla $ i = 1,2,...,n $ znajduje się po $ m $ liczb całkowitych $ a_{i,1}, a_{i,2}, ..., a_{i,m} $ ($ 0 \leq a_{i,j} \leq p-1 $) - liczb które rosną na poletkach od $ (i,1) $ do $ (i,m) $

Kolejna linia zawiera jedną liczbę całkowitą $ t $ - liczbę zapytań o prostokąty.($ 1 \leq t \leq 100000) $. W kolejnych $ t $ liniach znajdują się czwórki liczb całkowitych $ x_{1},y_{1},x_{2},y_{2} $ - współrzędne lewego górnego i prawego dolnego rogu prostokąta. (Zatem prostokąt składa się z poletek $ a_{i,j} $ dla $ x_{1} \leq i \leq x_{2} $ i $ y_{1} \leq j \leq y_{2} $, ponadto $ 1 \leq x_{1} \leq x_{2} \leq n, 1 \leq y_{1} \leq y_{2} \leq m $).

Wyjście:

Dla każdego zapytania należy wypisać jedną liczbę calkowitą - iloczyn liczb z poletek znajdujących się w prostokącie modulo $ p $.

Przykład:

Wejście:

4 5 11
1 3 0 7 6
0 0 2 4 9
4 2 1 1 5
0 6 0 8 0
3
1 1 2 2
2 3 3 5
3 1 3 1

Wyjście:

0
8
4
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasŻniwa
1Bartosz Tarnawski1006:32:5810
2Wojciech Szałapski1031:09:3810
3Bartek Dudek10146:18:4010
4Mateusz Wasylkiewicz10153:57:1010
5Wojtek Nadara10173:05:4610
6Piotr Bejda10173:17:3710
7Kamil Dębowski10173:19:3710
8Przemysław Derengowski10173:40:1310
9Damian Straszak10341:23:2710
10Witold Długosz10369:47:5110
11Krzysztof Drab628:32:116
12Krzysztof Cirocki5148:53:385
13Andrzej Rumiński4174:39:394
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com