#include <bits/stdc++.h>
using namespace std;
#include "rect.h"
//#define HOME
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x<< "\n"
const int N = 2500;
int prvX[N][N], prvY[N][N], nxtX[N][N], nxtY[N][N];
inline bool check (int x1, int y1, int x2, int y2, int n, int m) {
if (x1 > 0 && y1 > 0 && x2 < n - 1 && y2 < m - 1) {
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (prvX[i][j] < y1 - 1) return false;
if (prvY[i][j] < x1 - 1) return false;
if (nxtX[i][j] > y2 + 1) return false;
if (nxtY[i][j] > x2 + 1) return false;
}
}
return true;
}
return false;
}
ll count_rectangles (vector <vector <int>> a) {
int n = a.size ();
int m = a[0].size ();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prvX[i][j] = j - 1;
while (prvX[i][j] >= 0 && a[i][prvX[i][j]] <= a[i][j])
prvX[i][j] = prvX[i][prvX[i][j]];
}
for (int j = m - 1; j >= 0; j--) {
nxtX[i][j] = j + 1;
while (nxtX[i][j] < m && a[i][nxtX[i][j]] <= a[i][j])
nxtX[i][j] = nxtX[i][nxtX[i][j]];
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
prvY[i][j] = i - 1;
while (prvY[i][j] >= 0 && a[prvY[i][j]][j] <= a[i][j])
prvY[i][j] = prvY[prvY[i][j]][j];
}
for (int i = n - 1; i >= 0; i--) {
nxtY[i][j] = i + 1;
while (nxtY[i][j] < n && a[nxtY[i][j]][j] <= a[i][j])
nxtY[i][j] = nxtY[nxtY[i][j]][j];
}
}
set <pair <pair <int, int>, pair <int, int>>> ans;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (check (prvY[i][j] + 1, prvX[i][j] + 1, nxtY[i][j] - 1, nxtX[i][j] - 1, n, m))
ans.insert ({{prvY[i][j] + 1, prvX[i][j] + 1}, {nxtY[i][j] - 1, nxtX[i][j] - 1}});
return (int) ans.size ();
}
#ifdef HOME
int main() {
int n, m;
cin >> n >> m;
vector <vector <int>> a (n, vector <int> (m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
cout << count_rectangles (a) << "\n";
return 0;
}
#endif
/**
6 5
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
**/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
896 KB |
Output is correct |
20 |
Correct |
1 ms |
896 KB |
Output is correct |
21 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
16 ms |
2176 KB |
Output is correct |
18 |
Correct |
17 ms |
2176 KB |
Output is correct |
19 |
Correct |
17 ms |
2176 KB |
Output is correct |
20 |
Correct |
2 ms |
2048 KB |
Output is correct |
21 |
Correct |
2 ms |
1912 KB |
Output is correct |
22 |
Correct |
2 ms |
1912 KB |
Output is correct |
23 |
Correct |
3 ms |
1920 KB |
Output is correct |
24 |
Correct |
2 ms |
1792 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
896 KB |
Output is correct |
28 |
Correct |
1 ms |
896 KB |
Output is correct |
29 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
16 ms |
2176 KB |
Output is correct |
18 |
Correct |
17 ms |
2176 KB |
Output is correct |
19 |
Correct |
17 ms |
2176 KB |
Output is correct |
20 |
Correct |
2 ms |
2048 KB |
Output is correct |
21 |
Correct |
2 ms |
1912 KB |
Output is correct |
22 |
Correct |
2 ms |
1912 KB |
Output is correct |
23 |
Correct |
3 ms |
1920 KB |
Output is correct |
24 |
Correct |
2 ms |
1792 KB |
Output is correct |
25 |
Correct |
547 ms |
7256 KB |
Output is correct |
26 |
Correct |
561 ms |
7160 KB |
Output is correct |
27 |
Correct |
554 ms |
7268 KB |
Output is correct |
28 |
Correct |
7 ms |
4736 KB |
Output is correct |
29 |
Correct |
9 ms |
5504 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
18 ms |
5632 KB |
Output is correct |
32 |
Correct |
14 ms |
5632 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
896 KB |
Output is correct |
36 |
Correct |
1 ms |
896 KB |
Output is correct |
37 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
16 ms |
2176 KB |
Output is correct |
18 |
Correct |
17 ms |
2176 KB |
Output is correct |
19 |
Correct |
17 ms |
2176 KB |
Output is correct |
20 |
Correct |
2 ms |
2048 KB |
Output is correct |
21 |
Correct |
2 ms |
1912 KB |
Output is correct |
22 |
Correct |
2 ms |
1912 KB |
Output is correct |
23 |
Correct |
3 ms |
1920 KB |
Output is correct |
24 |
Correct |
2 ms |
1792 KB |
Output is correct |
25 |
Correct |
547 ms |
7256 KB |
Output is correct |
26 |
Correct |
561 ms |
7160 KB |
Output is correct |
27 |
Correct |
554 ms |
7268 KB |
Output is correct |
28 |
Correct |
7 ms |
4736 KB |
Output is correct |
29 |
Correct |
9 ms |
5504 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
18 ms |
5632 KB |
Output is correct |
32 |
Correct |
14 ms |
5632 KB |
Output is correct |
33 |
Correct |
49 ms |
26372 KB |
Output is correct |
34 |
Correct |
45 ms |
26232 KB |
Output is correct |
35 |
Correct |
46 ms |
26360 KB |
Output is correct |
36 |
Correct |
48 ms |
26232 KB |
Output is correct |
37 |
Execution timed out |
5022 ms |
27408 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
768 KB |
Output is correct |
2 |
Correct |
4 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
302 ms |
83976 KB |
Output is correct |
3 |
Correct |
647 ms |
174584 KB |
Output is correct |
4 |
Correct |
674 ms |
175228 KB |
Output is correct |
5 |
Correct |
660 ms |
175352 KB |
Output is correct |
6 |
Correct |
214 ms |
78968 KB |
Output is correct |
7 |
Correct |
377 ms |
155644 KB |
Output is correct |
8 |
Correct |
393 ms |
159560 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
896 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
16 ms |
2176 KB |
Output is correct |
18 |
Correct |
17 ms |
2176 KB |
Output is correct |
19 |
Correct |
17 ms |
2176 KB |
Output is correct |
20 |
Correct |
2 ms |
2048 KB |
Output is correct |
21 |
Correct |
2 ms |
1912 KB |
Output is correct |
22 |
Correct |
2 ms |
1912 KB |
Output is correct |
23 |
Correct |
3 ms |
1920 KB |
Output is correct |
24 |
Correct |
2 ms |
1792 KB |
Output is correct |
25 |
Correct |
547 ms |
7256 KB |
Output is correct |
26 |
Correct |
561 ms |
7160 KB |
Output is correct |
27 |
Correct |
554 ms |
7268 KB |
Output is correct |
28 |
Correct |
7 ms |
4736 KB |
Output is correct |
29 |
Correct |
9 ms |
5504 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
18 ms |
5632 KB |
Output is correct |
32 |
Correct |
14 ms |
5632 KB |
Output is correct |
33 |
Correct |
49 ms |
26372 KB |
Output is correct |
34 |
Correct |
45 ms |
26232 KB |
Output is correct |
35 |
Correct |
46 ms |
26360 KB |
Output is correct |
36 |
Correct |
48 ms |
26232 KB |
Output is correct |
37 |
Execution timed out |
5022 ms |
27408 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |