This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m));
//right
for(int i=0; i<n; i++){
stack<int> s;
for(int j=0; j<m; j++){
while(s.size() and a[i][s.top()] < a[i][j]){
right[i][s.top()] = j;
s.pop();
}
s.push(j);
}
}
//left
for(int i=0; i<n; i++){
stack<int> s;
for(int j=m-1; j>=0; j--){
while(s.size() and a[i][s.top()] < a[i][j]){
left[i][s.top()] = j;
s.pop();
}
s.push(j);
}
}
//up
for(int j=0; j<m; j++){
stack<int> s;
for(int i=n-1; i>=0; i--){
while(s.size() and a[s.top()][j] < a[i][j]){
up[s.top()][j] = i;
s.pop();
}
s.push(i);
}
}
//down
for(int j=0; j<m; j++){
stack<int> s;
for(int i=0; i<n; i++){
while(s.size() and a[s.top()][j] < a[i][j]){
down[s.top()][j] = i;
s.pop();
}
s.push(i);
}
}
vector<vector<array<int, 4>>> borders(n, vector<array<int, 4>>(m, {m, -1, n, -1}));
auto merge = [&](int x1, int y1, int x2, int y2){
borders[x1][y1][0] = min(borders[x1][y1][0], borders[x2][y2][0]);
borders[x1][y1][1] = max(borders[x1][y1][1], borders[x2][y2][1]);
borders[x1][y1][2] = min(borders[x1][y1][2], borders[x2][y2][2]);
borders[x1][y1][3] = max(borders[x1][y1][3], borders[x2][y2][3]);
};
vector<pair<int,int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> vis(n, vector<int>(m));
auto dfs = [&](auto &&dfs, int i, int j){
vis[i][j] = 1;
borders[i][j] = {left[i][j], right[i][j], up[i][j], down[i][j]};
if(i == 0 or i == n-1 or j == 0 or j == m-1) return;
for(auto [di, dj]: dir){
if(a[i][j] < a[i+di][j+dj]) continue;
if(!vis[i+di][j+dj]) dfs(dfs, i+di, j+dj);
merge(i, j, i+di, j+dj);
}
};
vector<array<int, 3>> pts;
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
pts.push_back({a[i][j], i, j});
}
}
vector<array<int, 4>> rects;
for(auto [h, i, j]: pts){
if(!vis[i][j]) dfs(dfs, i, j);
int l = left[i][j], r = right[i][j], u = up[i][j], d = down[i][j];
if(l == -1 or r == m or u == -1 or d == n) continue;
if(
borders[i][j][0] == l and
borders[i][j][1] == r and
borders[i][j][2] == u and
borders[i][j][3] == d
) rects.push_back({l, r, u, d});
}
// for(int i=0; i<n; i++){
// for(int j=0; j<m; j++){
// cout << left[i][j] << " ";
// }
// cout << endl;
// }
sort(rects.begin(), rects.end());
return unique(rects.begin(), rects.end()) - rects.begin();
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣠⣤⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⡴⡖⣻⡟⣛⡛⣿⣿⣿⣿⣻⣿⣿⡟⠛⠳⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣯⣾⣤⣹⣷⣿⣿⡿⣿⡿⣿⣿⣿⣿⣼⣧⣄⣚⠉⠛⠶⢶⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣙⠾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢘⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⠛⠛⠛⠛⠿⠿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⡿⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⣿⣿⣯⡿⠀⠀⠀⠀⠀⠀⠀⠠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⣀⣄⡀⠀⠀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⡇⣠⣾⣿⣿⣶⣶⣶⣶⣿⣦⡀⠀⠻⣤⣶⣾⣿⣿⣿⣿⣿⠿⠿⣿⣶⣄⠈⣿⡇⢹⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⠁⡿⠟⣉⣽⣿⣿⣿⣿⣿⣿⡗⠀⠀⢈⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣦⣹⡇⣽⣿⣿⣿⣿⣿⣿⣿⠀⣀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⠴⠂⠀⣀⣤⣾⣿⣿⣿⣿⣿⡿⠀⢱⣿⣿⣏⣛⣛⣣⢬⣹⢿⠏⠀⢀⣼⣿⣯⡛⠒⢽⣿⣥⡿⣿⣿⣿⣿⣿⣿⣇⣿⣿⣿⣿⣿⣿⣿⣍⣉⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣰⣿⠤⣶⣿⠿⣻⣿⣿⣿⣿⣿⣿⡇⠀⠀⠋⠀⠉⠉⠁⠒⠉⠀⠀⡀⠀⠀⢿⣿⣿⠛⠦⠀⠀⢸⡿⠋⠋⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡛⣆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠉⠉⢡⣰⣥⠾⣿⣿⣿⣿⣿⣿⣿⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⢸⡿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⣿⣿⡹⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⡕⠽⣾⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣶⣶⣤⣶⣿⣷⣼⣧⡀⠀⠀⠀⠠⠀⢀⣰⣿⣿⣿⣿⣿⣿⣷⣻⣿⣿⣿⣿⣿⣿⢿⣿⣶⠄
⠀⠀⠀⠀⠀⠀⠀⠀⡞⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⢠⠎⠻⠯⣍⠙⠟⢻⣿⠿⣿⠟⠀⠀⠀⣶⣦⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⠳⣌⢣⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣡⠖⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀⠈⠀⢀⣴⣿⠟⠁⢾⣿⣷⣄⡀⡀⠀⠀⠿⠟⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠈⠁⠀⣧
⠀⠀⠀⠀⠀⠀⠀⣼⠃⠀⠀⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡤⠀⠀⠀⣠⣾⣾⠟⢛⣁⣤⣠⣼⣿⣿⣿⣿⣿⣶⣄⣠⣾⣫⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠙⠷⣦⣾⣿⠟⢿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⣱⠀⣼⣿⡯⡿⠾⠛⠛⠛⠛⠛⢻⣿⣿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠋⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣷⣿⣷⠃⢿⡟⠀⠀⠰⣦⣤⣤⣴⣶⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡶⢿⣷⣦⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠈⠀⠀⠀⠀⠀⠛⠉⠛⠛⠛⠻⣿⢟⣉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠘⣼⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⣽⣷⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣷⣶⣠⣤⣠⣦⡡⣠⣼⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠦⣽⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⠉⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⠟⠛⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣟⡿⣻⣿⠟⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣟⡛⠁⠘⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢀⣀⣀⣀⣀⣀⣤⢴⣾⠿⣉⣽⠞⠁⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣻⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⡿⠒⠾⣿⣭⣌⡉⠉⠙⠳⠟⢁⣐⠛⠃⠀⢐⡶⠉⠉⠻⣿⣿⣿⣿⣯⡙⢿⣯⣉⠉⠻⣿⣿⣏⢿⣿⣿⣿⣿⣿⣬⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣧⢐⡦⣌⠙⢮⡹⠛⢶⣤⣶⣯⣍⢰⠋⠄⠘⠁⠀⠀⠀⠈⠍⠛⠻⢿⣿⣷⣍⡻⣿⣶⣮⣙⠿⢾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⠆⣈⠵⠶⠈⢺⡉⠙⠿⣿⣿⣿⣷⡷⠂⠀⠀⠀⠰⣾⡄⢀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⢿⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣍⣽⣿⡜⣆⠳⣯⡲⣤⣀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⡌⡄⠀⠀⠀⠀⠙⢶⣄⠀⠙⢿⣿⣟⣀⠀⠀⠀⠀⠈⢿⣾⡇⠀⠀⠀⣮⢙⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣛⣿⣿⣿⣿⣿⣿⣿⣿⡿⠉⢿⡀⠀⠙⢿⣎⢿⣿⣶⣤⣀⠀⠀⠀
⣿⣿⣷⡹⠀⠀⠀⠀⠀⠀⠈⠻⢦⣄⡙⢻⣿⣾⣤⡀⠀⠀⠈⢿⣿⡀⠀⠀⠹⣾⠟⣿⣿⣿⣿⣿⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⠿⡛⠑⠀⠂⠸⡿⠝⠀⠄⢻⣧⢻⣆⠉⡹⠿⣿⡂
⣿⣿⣿⣏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢻⣿⣿⣿⣿⣷⣄⣀⠈⣿⣷⣄⠀⠘⠙⠰⢿⣿⣿⣿⣿⣿⣿⣧⣚⣿⣿⣯⡋⠄⠰⢉⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣧⢻⣦⠘⡇⠈⠛
⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠈⠉⠙⠛⠛⠻⠾⣿⣿⣟⣷⠀⠀⢪⠙⢿⣿⣿⢿⣿⣿⠙⢻⣿⣿⠁⠶⠔⠈⢑⠋⠀⠀⠀⠀⠀⡀⠀⠀⢿⣿⣧⣙⠦⢻⡀⠀
⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⡆⠀⠘⠷⣷⣧⣽⣾⣯⣿⡗⠸⣿⣿⠀⠠⢰⠚⠊⠀⠂⠀⠀⠀⠀⡌⠈⠒⠘⡿⡁⢹⣶⣾⡇⠀
⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡇⢀⠀⠀⠸⡏⡿⢷⣜⢿⡇⠀⣿⣿⡀⠆⢀⠀⠂⠀⠀⡀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⢿⡿⠁⠀
⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣆⠀⠀⠀⠁⠀⠀⠙⣿⡇⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠈⠂⠀⠐⠁⠀⠀⠀⠀⠀⠀⢸⠅⠀⠀
⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⣦⡀⠀⠀⠀⠀⠀⠃⣿⠀⣿⣿⡇⢀⠀⠀⠀⠀⠀⠀⠀⠘⠆⠀⠀⠀⠀⠀⠀⠀⡸⣦⠀⢀
⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⡄⠀⣸⣿⡄⠀⡏⠀⢿⢿⡇⠀⠄⠀⠀⠘⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⡄⠀⠀⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠙⡽⢣⡜⠐⠹⠆⠁⠀⢺⣿⡇⠀⠀⠀⠀⠀⠀⢡⡂⠐⠀⠂⢤⡀⠈⠀⠀⠀⢀⣿⣿⣿
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |