Zemljiški kataster

Osnovne informacije

Omejitve
  • Čas: 15 s
  • Spomin: 512 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Na Geodetski upravi so naleteli na zanimiv primer pravokotnega zemljišča, ki je razdeljeno na parcele. Zemljišče je predstavljeno s pravokotno mrežo z N vrsticami in M stolpci. Vsako polje v tej mreži pa vsebuje celoštevilsko oznako. Oznake so dodeljene tako, da vsaka povezana komponenta polj z enakimi oznakami ustreza posamezni parceli. Dve polji pripadata isti povezani komponenti oz. parceli, če si delita stranico in imata enako oznako.

Geodete zanima, koliko parcel se nahaja na zemljišču, če bi se omejili samo na določen pas zemljišča od vključno stolpca A_i do B_i. V vsaki poizvedbi se omejimo samo na podano območje zemljišča (kot da preostanek ne bi obstajal). Če sta torej dve polji z enako oznako povezani preko polj izven podanega območja, ju upoštevamo kot ločeni parceli.

Vhodni podatki

V prvi vrstici se nahajata višina N in širina M. Vsaka od naslednjih N vrstic vsebuje M s presledki ločenih števil X_{i,j}, ki opisujejo oznake polj. Sledi število poizvedb Q in opis poizvedb z levim robom območja A_i in desnim B_i.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10^4
  • 1 \leq Q \leq 10^5
  • 0 \leq X_{i,j} < 10^9
  • 1 \leq A_i \leq B_i \leq M

Izhodni podatki

Za vsako poizvedbo izpišite v svoji vrstici iskano število komponent na podanem območju, tj. od stolpca A_i do B_i.

Primer

Vhod

5 9
1 1 1 1 2 4 4 4 1
1 2 2 1 2 1 1 4 1
1 2 1 1 2 0 1 4 1
1 2 2 2 2 1 1 4 1
1 1 1 1 1 4 4 4 1
4
3 3
3 4
1 4
4 7

Izhod

5
4
2
7

Komentar

Spodnja slika prikazuje zgornji primer testnih podatkov. Na sliki so posamezne parcele označene z isto barvo.

Ilustracija primerov

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task