Ορθογώνια

Στα μέσα του 18ου αιώνα, o ηγέτης Χαν Σαρδάμογλου διέταξε να χτιστεί ένα παλάτι σε ένα οροπέδιο. Το οροπέδιο αναπαρίσταται με ένα πλέγμα αποτελούμενο από ~n~ x ~m~ τετράγωνα. Οι γραμμές του οροπεδίου είναι αριθμημένες από το ~0~ μέχρι το ~n - 1~ και οι στήλες από το ~0~ μέχρι το ~m - 1~. Συμβολίζουμε με (~i, j~) το τετράγωνο της γραμμής ~i~ και της στήλης ~j~ (~0 \le i \le n - 1~, ~0 \le j \le m - 1~). Κάθε τετράγωνο (~i, j~) έχει ένα συγκεκριμένο ύψος που συμβολίζεται με ~a[i][j]~.

Ο Χαν ζήτησε από τους αρχιτέκτονές του να επιλέξουν μια ορθογώνια περιοχή για να χτιστεί το παλάτι. Η περιοχή δεν πρέπει να περιέχει τετράγωνο από τα όρια του πλέγματος (γραμμή ~0~, γραμμή ~n - 1~, στήλη ~0~, και στήλη ~m - 1~), δηλαδή δεν πρέπει να αγγίζει τις άκρες του πλέγματος. Έτσι, οι αρχιτέκτονες έπρεπε να επιλέξουν τέσσερις ακέραιους ~r_1~, ~r_2~, ~c_1~ και ~c_2~ (~1 \le r_1 \le r_2 \le n - 2~ και ~1 \le c_1 \le c_2 \le m - 2~), οι οποίοι ορίζουν την περιοχή που περιέχει όλα τα τετράγωνα (~i, j~), έτσι ώστε ~r_1 \le i \le r_2~ και ~c_1 \le j \le c_2~.

Επιπλέον, μια περιοχή θεωρείται έγκυρη, αν και μόνο αν για κάθε τετράγωνο (~i, j~) στη περιοχή ισχύει η παρακάτω συνθήκη:

• Θεωρήστε τα δυο τετράγωνα γειτονικά της περιοχής που βρίσκονται στη γραμμή ~i~ (τα τετραγωνάκια (~i, c_1 - 1~) και (~i, c_2 + 1~)) και τα δυο τετράγωνα γειτονικά της περιοχής που βρίσκονται στη στήλη ~j~ (τα τετράγωνα (~r_1 - 1, j~) και (~r_2 + 1, j~)). Το ύψος του τετραγώνου (~i, j~) θα πρέπει να είναι αυστηρά μικρότερο από τα ύψη όλων αυτών των τεσσάρων τετραγώνων.

Βοηθήστε τους αρχιτέκτονες να βρουν το πλήθος των έγκυρων περιοχών για το παλάτι (δηλαδή, το πλήθος των επιλογών των ~r_1~, ~r_2~, ~c_1~ και ~c_2~ που ορίζουν έγκυρες περιοχές).

Λεπτομέρειες υλοποίησης

Θα πρέπει να υλοποιήσετε μια συνάρτηση:

int64 count_rectangles(int[][] a)

• ~a~: ένας διδιάστατος πίνακας ~n~ x ~m~ ακέραιων που αναπαριστούν τα ύψη των τετραγώνων.
• Αυτή η συνάρτηση πρέπει να επιστρέφει το πλήθος των έγκυρων περιοχών.

Παραδείγματα

Παράδειγμα 1

Έστω ότι έχουμε την ακόλουθη κλήση της συνάρτησης.

count_rectangles([[4, 8, 7, 5, 6],
                 [7, 4, 10, 3, 5],
                 [9, 7, 20, 14, 2],
                 [9, 14, 7, 3, 6],
                 [5, 7, 5, 2, 7],
                 [4, 5, 13, 5, 6]])

Υπάρχουν έγκυρες περιοχές:

• ~r_1 = r_2 = c_1 = c_2 = 1~
• ~r_1 = 1, r_2 = 2, c_1 = c_2 = 1~
• ~r_1 = r_2 = 1, c_1 = c_2 = 3~
• ~r_1 = r_2 = 4, c_1 = 2, c_2 = 3~
• ~r_1 = r_2 = 4, c_1 = c_2 = 3~
• ~r_1 = 3, r_2 = 4, c_1 = c_2 = 3~

Για παράδειγμα η περιοχή ~r_1 = 1, r_2 = 2, c_1 = c_2 = 1~ είναι έγκυρη γιατί ισχύουν οι δυο παρακάτω συνθήκες:

• το ~a[1][1] = 4~ είναι αυστηρά μικρότερο από τα ~a[0][1] = 8~, ~a[3][1] = 14~, ~a[1][0] = 7~ και ~a[1][2] = 10~.
• το ~a[2][1] = 7~ είναι αυστηρά μικρότερο από τα ~a[0][1] = 8~, ~a[3][1] = 14~, ~a[2][0] = 9~ και ~a[2][2] = 20~.

Περιορισμοί

• ~1 \le n, m \le 2\,500~
• ~0 \le a[i][j] \le 7\,000\,000~ (για κάθε ~0 \le i \le n - 1~, ~0 \le j \le m - 1~)

Υποπροβλήματα

1. (~8~ βαθμοί) ~n, m \le 30~
2. (~7~ βαθμοί) ~n, m \le 80~
3. (~12~ βαθμοί) ~n, m \le 200~
4. (~22~ βαθμοί) ~n, m \le 700~
5. (~10~ βαθμοί) ~n \le 3~
6. (~13~ βαθμοί) ~0 \le a[i][j] \le 1~ (για κάθε ~0 \le i \le n - 1~, ~0 \le j \le m - 1~)
7. (~28~ βαθμοί) Κανένας επιπλέον περιορισμός.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~ ~m~
• γραμμή ~2 + i~ (για ~0 \le i \le n - 1~): ~a[i][0]~ ~a[i][1] ... a[i][m - 1]~

Ο υποδειγματικός βαθμολογητής τυπώνει μία μόνο γραμμή, που περιέχει την τιμή που επιστρέφει η συνάρτηση count_rectangles.