#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll count_rectangles(vector<vector<int>> a) {
int n = (int) a.size(), m = (int) a[0].size();
vector<vector<int>> cp(n, vector<int>(m, -1)), cn(n, vector<int>(m, -1));
vector<vector<int>> rp(n, vector<int>(m, -1)), rn(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
stack<int> s;
for (int j = 0; j < m; j++) {
while (!s.empty() && a[i][j] > a[i][s.top()])
cn[i][s.top()] = j, s.pop();
if (!s.empty())
cp[i][j] = a[i][j] < a[i][s.top()] ? s.top() : cp[i][s.top()];
s.push(j);
}
}
for (int j = 0; j < m; j++) {
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[i][j] > a[s.top()][j])
rn[s.top()][j] = i, s.pop();
if (!s.empty())
rp[i][j] = a[i][j] < a[s.top()][j] ? s.top() : rp[s.top()][j];
s.push(i);
}
}
vector<vector<bool>> valid(n, vector<bool>(m, true));
vector<int> cpr(m * m), cpl(m * m, -2), rpc(n * n, -2), rpl(n * n, -2);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = cp[i][j] * m + cn[i][j];
if (cpl[x] < i - 1)
cpr[x] = i;
cpl[x] = i;
valid[i][j] = valid[i][j] && cpr[x] <= rp[i][j] + 1;
}
for (int j = 0; j < m; j++)
for (int i = 0; i < n; i++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = rp[i][j] * n + rn[i][j];
if (rpl[x] < j - 1)
rpc[x] = j;
rpl[x] = j;
valid[i][j] = valid[i][j] && rpc[x] <= cp[i][j] + 1;
}
cpl.assign(m * m, n + 1);
rpl.assign(n * n, m + 1);
for (int i = n - 1; i >= 0; i--)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = cp[i][j] * m + cn[i][j];
if (cpl[x] > i + 1)
cpr[x] = i;
cpl[x] = i;
valid[i][j] = valid[i][j] && cpr[x] >= rn[i][j] - 1;
}
for (int j = m - 1; j >= 0; j--)
for (int i = 0; i < n; i++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = rp[i][j] * n + rn[i][j];
if (rpl[x] > j + 1)
rpc[x] = j;
rpl[x] = j;
valid[i][j] = valid[i][j] && rpc[x] >= cn[i][j] - 1;
}
int res = 0;
unordered_set<ll> rect;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1 && valid[i][j]) {
ll x = ((ll) (cp[i][j] * m + cn[i][j]) * n + rp[i][j]) * n + rn[i][j];
if (rect.find(x) == rect.end())
res++, rect.insert(x);
}
return res;
}
// int main() {
// int n = 2500, m = 2500;
// vector<vector<int>> a(n, vector<int>(m));
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)
// a[i][j] = max(i, n - i) + max(j, m - j);
// cout << count_rectangles(a) << "\n";
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
296 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
296 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
2 ms |
852 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
872 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
2 ms |
596 KB |
Output is correct |
27 |
Correct |
3 ms |
596 KB |
Output is correct |
28 |
Correct |
2 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
852 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
2 ms |
872 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
1 ms |
436 KB |
Output is correct |
25 |
Correct |
0 ms |
296 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
8 ms |
3632 KB |
Output is correct |
31 |
Correct |
9 ms |
3728 KB |
Output is correct |
32 |
Correct |
10 ms |
3752 KB |
Output is correct |
33 |
Correct |
6 ms |
2132 KB |
Output is correct |
34 |
Correct |
9 ms |
2644 KB |
Output is correct |
35 |
Correct |
10 ms |
2808 KB |
Output is correct |
36 |
Correct |
10 ms |
2696 KB |
Output is correct |
37 |
Correct |
10 ms |
2772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
852 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
2 ms |
872 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
1 ms |
436 KB |
Output is correct |
25 |
Correct |
8 ms |
3632 KB |
Output is correct |
26 |
Correct |
9 ms |
3728 KB |
Output is correct |
27 |
Correct |
10 ms |
3752 KB |
Output is correct |
28 |
Correct |
6 ms |
2132 KB |
Output is correct |
29 |
Correct |
9 ms |
2644 KB |
Output is correct |
30 |
Correct |
10 ms |
2808 KB |
Output is correct |
31 |
Correct |
10 ms |
2696 KB |
Output is correct |
32 |
Correct |
10 ms |
2772 KB |
Output is correct |
33 |
Correct |
0 ms |
296 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
40 ms |
20988 KB |
Output is correct |
39 |
Correct |
52 ms |
21036 KB |
Output is correct |
40 |
Correct |
47 ms |
20932 KB |
Output is correct |
41 |
Correct |
54 ms |
21004 KB |
Output is correct |
42 |
Correct |
143 ms |
41792 KB |
Output is correct |
43 |
Correct |
133 ms |
41740 KB |
Output is correct |
44 |
Correct |
146 ms |
41904 KB |
Output is correct |
45 |
Correct |
156 ms |
39552 KB |
Output is correct |
46 |
Correct |
95 ms |
21424 KB |
Output is correct |
47 |
Correct |
91 ms |
22980 KB |
Output is correct |
48 |
Correct |
122 ms |
27552 KB |
Output is correct |
49 |
Correct |
136 ms |
27548 KB |
Output is correct |
50 |
Correct |
59 ms |
15548 KB |
Output is correct |
51 |
Correct |
60 ms |
15520 KB |
Output is correct |
52 |
Correct |
150 ms |
27492 KB |
Output is correct |
53 |
Correct |
140 ms |
27584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
49492 KB |
Output is correct |
2 |
Correct |
20 ms |
35780 KB |
Output is correct |
3 |
Correct |
25 ms |
49360 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
27 ms |
49460 KB |
Output is correct |
6 |
Correct |
28 ms |
49472 KB |
Output is correct |
7 |
Correct |
34 ms |
49444 KB |
Output is correct |
8 |
Correct |
30 ms |
49432 KB |
Output is correct |
9 |
Correct |
27 ms |
49364 KB |
Output is correct |
10 |
Correct |
25 ms |
49192 KB |
Output is correct |
11 |
Correct |
28 ms |
49372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
635 ms |
128584 KB |
Output is correct |
8 |
Correct |
1390 ms |
256840 KB |
Output is correct |
9 |
Correct |
1403 ms |
258092 KB |
Output is correct |
10 |
Correct |
1393 ms |
258208 KB |
Output is correct |
11 |
Correct |
197 ms |
135612 KB |
Output is correct |
12 |
Correct |
390 ms |
232572 KB |
Output is correct |
13 |
Correct |
469 ms |
247644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
852 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
2 ms |
872 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
2 ms |
596 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
1 ms |
436 KB |
Output is correct |
25 |
Correct |
8 ms |
3632 KB |
Output is correct |
26 |
Correct |
9 ms |
3728 KB |
Output is correct |
27 |
Correct |
10 ms |
3752 KB |
Output is correct |
28 |
Correct |
6 ms |
2132 KB |
Output is correct |
29 |
Correct |
9 ms |
2644 KB |
Output is correct |
30 |
Correct |
10 ms |
2808 KB |
Output is correct |
31 |
Correct |
10 ms |
2696 KB |
Output is correct |
32 |
Correct |
10 ms |
2772 KB |
Output is correct |
33 |
Correct |
40 ms |
20988 KB |
Output is correct |
34 |
Correct |
52 ms |
21036 KB |
Output is correct |
35 |
Correct |
47 ms |
20932 KB |
Output is correct |
36 |
Correct |
54 ms |
21004 KB |
Output is correct |
37 |
Correct |
143 ms |
41792 KB |
Output is correct |
38 |
Correct |
133 ms |
41740 KB |
Output is correct |
39 |
Correct |
146 ms |
41904 KB |
Output is correct |
40 |
Correct |
156 ms |
39552 KB |
Output is correct |
41 |
Correct |
95 ms |
21424 KB |
Output is correct |
42 |
Correct |
91 ms |
22980 KB |
Output is correct |
43 |
Correct |
122 ms |
27552 KB |
Output is correct |
44 |
Correct |
136 ms |
27548 KB |
Output is correct |
45 |
Correct |
59 ms |
15548 KB |
Output is correct |
46 |
Correct |
60 ms |
15520 KB |
Output is correct |
47 |
Correct |
150 ms |
27492 KB |
Output is correct |
48 |
Correct |
140 ms |
27584 KB |
Output is correct |
49 |
Correct |
26 ms |
49492 KB |
Output is correct |
50 |
Correct |
20 ms |
35780 KB |
Output is correct |
51 |
Correct |
25 ms |
49360 KB |
Output is correct |
52 |
Correct |
0 ms |
212 KB |
Output is correct |
53 |
Correct |
27 ms |
49460 KB |
Output is correct |
54 |
Correct |
28 ms |
49472 KB |
Output is correct |
55 |
Correct |
34 ms |
49444 KB |
Output is correct |
56 |
Correct |
30 ms |
49432 KB |
Output is correct |
57 |
Correct |
27 ms |
49364 KB |
Output is correct |
58 |
Correct |
25 ms |
49192 KB |
Output is correct |
59 |
Correct |
28 ms |
49372 KB |
Output is correct |
60 |
Correct |
1 ms |
212 KB |
Output is correct |
61 |
Correct |
635 ms |
128584 KB |
Output is correct |
62 |
Correct |
1390 ms |
256840 KB |
Output is correct |
63 |
Correct |
1403 ms |
258092 KB |
Output is correct |
64 |
Correct |
1393 ms |
258208 KB |
Output is correct |
65 |
Correct |
197 ms |
135612 KB |
Output is correct |
66 |
Correct |
390 ms |
232572 KB |
Output is correct |
67 |
Correct |
469 ms |
247644 KB |
Output is correct |
68 |
Correct |
0 ms |
296 KB |
Output is correct |
69 |
Correct |
1 ms |
212 KB |
Output is correct |
70 |
Correct |
1 ms |
340 KB |
Output is correct |
71 |
Correct |
1 ms |
212 KB |
Output is correct |
72 |
Correct |
1 ms |
212 KB |
Output is correct |
73 |
Correct |
694 ms |
247712 KB |
Output is correct |
74 |
Correct |
752 ms |
247792 KB |
Output is correct |
75 |
Correct |
784 ms |
247792 KB |
Output is correct |
76 |
Correct |
842 ms |
247792 KB |
Output is correct |
77 |
Correct |
3312 ms |
574808 KB |
Output is correct |
78 |
Correct |
1612 ms |
207924 KB |
Output is correct |
79 |
Correct |
1540 ms |
216792 KB |
Output is correct |
80 |
Correct |
2888 ms |
336904 KB |
Output is correct |
81 |
Correct |
1638 ms |
208312 KB |
Output is correct |
82 |
Correct |
2268 ms |
280104 KB |
Output is correct |
83 |
Correct |
2976 ms |
337924 KB |
Output is correct |
84 |
Correct |
1649 ms |
207160 KB |
Output is correct |
85 |
Correct |
3002 ms |
360984 KB |
Output is correct |
86 |
Correct |
2889 ms |
351040 KB |
Output is correct |
87 |
Correct |
1693 ms |
348816 KB |
Output is correct |
88 |
Correct |
3480 ms |
599384 KB |
Output is correct |
89 |
Correct |
3488 ms |
595668 KB |
Output is correct |
90 |
Correct |
3457 ms |
594016 KB |
Output is correct |