Masala #1144

Xotira 64 MB Vaqt 1000 ms
14

Daryo

Rectangulariston mamlakati to’rtburchak shaklida bo’lib bizga \(H \times W\) to’rtburchakni eslatadi, ya’ni, bu mamlakat xaritasiga qaralganda \(H\) ta qator va \(W\) ta ustundan iborat mahallalardan iborat bo’lib, \(i\) - qatorning \(j\) - ustundagi mahallaning ixtiyoriy nuqtasi dengiz sathidan \(A_{i, j}\) balandlikda joylashgan.

Mamlakat prezidenti mamlakat uzra juda katta o’zgarishlar qilmoqchi. U biron bir  \(k(1 \le k < W)\) - ustunni tanlaydi va xaritadan qaraganda mamlakatni  \(k\) va \(k + 1\) - ustunlar orasidan daryo o’tkazadi. Shundan so’ng u mahallalarni birlashtiradi, agarda: mahallar o’zaro qo’shni(umumiy tomonga ega), dengiz sathidan bir xil balandlikda joylashgan hamda ularni yaqindagina o’tkazilgan dengiz ajratmasa.

Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan minimal mahallalar sonini aniqlang.


Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida ikkita butun son, \(H(1 \le H)\)  va \(W(2\le W)\) sonlari beriladi. Keyingi \(H\) ta qatorning har birida \(W\) tadan butun son, \(A_{i,j}(1\le i \le H, 1 \le j \le W, 1 \le A_{i, j} \le 10^9)\) har bir mahallaning dengiz sathidan balandligi kiritiladi. Bunda matritsa elementlar soni \(H \times W \le 500000\) ekanligi kafolotlanadi.

 


Chiquvchi ma'lumotlar:

Chiqish oqimida yagona butun son, Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan eng kam mahallalar sonini chop eting.


Misollar
# input.txt output.txt
1
4 4
1 1 1 3
2 2 1 3
2 1 1 3
2 2 2 2
4
2
5 8
1 2 2 5 5 5 5 5
1 1 2 2 5 6 5 6
1 1 1 1 6 6 5 6
1 1 3 1 1 6 7 6
1 4 1 1 1 6 6 6
8
Izoh:

1 - testga izoh. Daryo uchinchi va to’rtinchi ustun orasidan kesib o’tganda

1-mahallaga (1,1), (1,2), (1,3), (2,3), (3,2), (3,3) elementlardagi mahallalar birlashgan

2-mahallaga (2,1), (2,2), (3,1), (4,1), (4,2), (4,3) elementlardagi mahallalar birlashgan

3-mahallaga (1,4), (2,4), (3, 4) elementlardagi mahallalar birlashgan

4-mahallaga (4,4) elementdagi mahalla o’zi qolgan.