#include <bits/stdc++.h>
inline bool bad(int i, int j, std::vector <std::vector <int>> c[2], std::vector <std::vector <int>> r[2]) {
return c[0][i][j] == -1 || c[1][i][j] == -1 || r[1][i][j] == -1 || r[0][i][j] == -1;
}
long long count_rectangles(std::vector <std::vector <int>> g) {
int n = g.size();
int m = g[0].size();
std::vector <std::vector <int>> c[2], r[2];
c[0] = c[1] = r[0] = r[1] = std::vector <std::vector <int>> (n, std::vector <int> (m, -1));
std::vector <int> v;
for (int j = 0; j < m; j++, v.clear()) { for (int i = 0; i < n; i++) { int vb; while (v.size() && g[i][j] > g[vb = v.back()][j]) { r[1][vb][j] = i; v.pop_back(); } if (v.size()) { r[0][i][j] = vb; if (g[i][j] >= g[vb][j]) { r[0][i][j] = r[0][vb][j]; } } v.push_back(i); } }
for (int i = 0; i < n; i++, v.clear()) { for (int j = 0; j < m; j++) { int vb; while (v.size() && g[i][j] > g[i][vb = v.back()]) { c[1][i][vb] = j; v.pop_back(); } if (v.size()) { c[0][i][j] = vb; if (g[i][j] >= g[i][vb]) { c[0][i][j] = c[0][i][vb]; } } v.push_back(j); } }
bool ok[3000][3000];
memset(ok, true, sizeof(ok));
std::vector <int> cc[2] = { std::vector <int> (m * m), std::vector <int> (m * m, -42) }, rr[2] = { std::vector <int> (n * n, -42), std::vector <int> (n * n, -42) };
for (int i = 0; i < n; i++) { for (int j = 0, ind; j < m; j++) { if (!bad(i, j, c, r)) { if ((cc[1][ind = c[0][i][j] * m + c[1][i][j]]) < i - 1) { cc[0][ind] = i; } cc[1][ind] = i; ok[i][j] &= cc[0][ind] <= r[0][i][j] + 1; } } }
for (int j = 0; j < m; j++) { for (int i = 0, ind; i < n; i++) { if (!bad(i, j, c, r)) { if ((rr[1][ind = r[0][i][j] * n + r[1][i][j]]) < j - 1) { rr[0][ind] = j; } rr[1][ind] = j; ok[i][j] &= rr[0][ind] <= c[0][i][j] + 1; } } }
for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { cc[1][i * m + j] = n + 1; } }
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { rr[1][i * n + j] = m + 1; } }
for (int i = n - 1; ~i; i--) { for (int j = 0, ind; j < m; j++) { if (!bad(i, j, c, r)) { if ((cc[1][ind = c[0][i][j] * m + c[1][i][j]]) > i + 1) { cc[0][ind] = i; } cc[1][ind] = i; ok[i][j] &= cc[0][ind] >= r[1][i][j] - 1; } } }
for (int j = m - 1; ~j; j--) { for (int i = 0, ind; i < n; i++) { if (!bad(i, j, c, r)) { if ((rr[1][ind = r[0][i][j] * n + r[1][i][j]]) > j + 1) { rr[0][ind] = j; } rr[1][ind] = j; ok[i][j] &= rr[0][ind] >= c[1][i][j] - 1; } } }
long long ans = 0;
std::set <long long> st;
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!bad(i, j, c, r) && ok[i][j]) { long long chain = (((long long) c[0][i][j] * m + c[1][i][j]) * n + r[0][i][j]) * n + r[1][i][j]; ans += st.find(chain) == st.end(); st.insert(chain); } } }
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9044 KB |
Output is correct |
2 |
Correct |
5 ms |
9172 KB |
Output is correct |
3 |
Correct |
6 ms |
9172 KB |
Output is correct |
4 |
Correct |
5 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9128 KB |
Output is correct |
6 |
Correct |
5 ms |
9132 KB |
Output is correct |
7 |
Correct |
5 ms |
9060 KB |
Output is correct |
8 |
Correct |
5 ms |
9024 KB |
Output is correct |
9 |
Correct |
5 ms |
9044 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
6 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
9044 KB |
Output is correct |
13 |
Correct |
5 ms |
9044 KB |
Output is correct |
14 |
Correct |
4 ms |
9044 KB |
Output is correct |
15 |
Correct |
5 ms |
9044 KB |
Output is correct |
16 |
Correct |
6 ms |
9044 KB |
Output is correct |
17 |
Correct |
4 ms |
9016 KB |
Output is correct |
18 |
Correct |
4 ms |
9044 KB |
Output is correct |
19 |
Correct |
4 ms |
9044 KB |
Output is correct |
20 |
Correct |
5 ms |
9044 KB |
Output is correct |
21 |
Correct |
4 ms |
9044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9044 KB |
Output is correct |
2 |
Correct |
5 ms |
9172 KB |
Output is correct |
3 |
Correct |
6 ms |
9172 KB |
Output is correct |
4 |
Correct |
5 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9128 KB |
Output is correct |
6 |
Correct |
5 ms |
9132 KB |
Output is correct |
7 |
Correct |
5 ms |
9060 KB |
Output is correct |
8 |
Correct |
5 ms |
9024 KB |
Output is correct |
9 |
Correct |
5 ms |
9044 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
6 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
9044 KB |
Output is correct |
13 |
Correct |
5 ms |
9044 KB |
Output is correct |
14 |
Correct |
4 ms |
9044 KB |
Output is correct |
15 |
Correct |
5 ms |
9044 KB |
Output is correct |
16 |
Correct |
6 ms |
9044 KB |
Output is correct |
17 |
Correct |
4 ms |
9016 KB |
Output is correct |
18 |
Correct |
4 ms |
9044 KB |
Output is correct |
19 |
Correct |
4 ms |
9044 KB |
Output is correct |
20 |
Correct |
5 ms |
9044 KB |
Output is correct |
21 |
Correct |
4 ms |
9044 KB |
Output is correct |
22 |
Correct |
8 ms |
9564 KB |
Output is correct |
23 |
Correct |
9 ms |
9584 KB |
Output is correct |
24 |
Correct |
7 ms |
9684 KB |
Output is correct |
25 |
Correct |
6 ms |
9408 KB |
Output is correct |
26 |
Correct |
7 ms |
9428 KB |
Output is correct |
27 |
Correct |
7 ms |
9404 KB |
Output is correct |
28 |
Correct |
7 ms |
9488 KB |
Output is correct |
29 |
Correct |
5 ms |
9300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9044 KB |
Output is correct |
2 |
Correct |
5 ms |
9172 KB |
Output is correct |
3 |
Correct |
6 ms |
9172 KB |
Output is correct |
4 |
Correct |
5 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9128 KB |
Output is correct |
6 |
Correct |
5 ms |
9132 KB |
Output is correct |
7 |
Correct |
5 ms |
9060 KB |
Output is correct |
8 |
Correct |
5 ms |
9024 KB |
Output is correct |
9 |
Correct |
5 ms |
9044 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
6 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
9044 KB |
Output is correct |
13 |
Correct |
5 ms |
9044 KB |
Output is correct |
14 |
Correct |
4 ms |
9044 KB |
Output is correct |
15 |
Correct |
5 ms |
9044 KB |
Output is correct |
16 |
Correct |
6 ms |
9044 KB |
Output is correct |
17 |
Correct |
8 ms |
9564 KB |
Output is correct |
18 |
Correct |
9 ms |
9584 KB |
Output is correct |
19 |
Correct |
7 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9408 KB |
Output is correct |
21 |
Correct |
7 ms |
9428 KB |
Output is correct |
22 |
Correct |
7 ms |
9404 KB |
Output is correct |
23 |
Correct |
7 ms |
9488 KB |
Output is correct |
24 |
Correct |
5 ms |
9300 KB |
Output is correct |
25 |
Correct |
4 ms |
9016 KB |
Output is correct |
26 |
Correct |
4 ms |
9044 KB |
Output is correct |
27 |
Correct |
4 ms |
9044 KB |
Output is correct |
28 |
Correct |
5 ms |
9044 KB |
Output is correct |
29 |
Correct |
4 ms |
9044 KB |
Output is correct |
30 |
Correct |
18 ms |
12712 KB |
Output is correct |
31 |
Correct |
17 ms |
12712 KB |
Output is correct |
32 |
Correct |
17 ms |
12804 KB |
Output is correct |
33 |
Correct |
10 ms |
10964 KB |
Output is correct |
34 |
Correct |
15 ms |
11484 KB |
Output is correct |
35 |
Correct |
17 ms |
11624 KB |
Output is correct |
36 |
Correct |
16 ms |
11604 KB |
Output is correct |
37 |
Correct |
14 ms |
11576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9044 KB |
Output is correct |
2 |
Correct |
5 ms |
9172 KB |
Output is correct |
3 |
Correct |
6 ms |
9172 KB |
Output is correct |
4 |
Correct |
5 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9128 KB |
Output is correct |
6 |
Correct |
5 ms |
9132 KB |
Output is correct |
7 |
Correct |
5 ms |
9060 KB |
Output is correct |
8 |
Correct |
5 ms |
9024 KB |
Output is correct |
9 |
Correct |
5 ms |
9044 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
6 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
9044 KB |
Output is correct |
13 |
Correct |
5 ms |
9044 KB |
Output is correct |
14 |
Correct |
4 ms |
9044 KB |
Output is correct |
15 |
Correct |
5 ms |
9044 KB |
Output is correct |
16 |
Correct |
6 ms |
9044 KB |
Output is correct |
17 |
Correct |
8 ms |
9564 KB |
Output is correct |
18 |
Correct |
9 ms |
9584 KB |
Output is correct |
19 |
Correct |
7 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9408 KB |
Output is correct |
21 |
Correct |
7 ms |
9428 KB |
Output is correct |
22 |
Correct |
7 ms |
9404 KB |
Output is correct |
23 |
Correct |
7 ms |
9488 KB |
Output is correct |
24 |
Correct |
5 ms |
9300 KB |
Output is correct |
25 |
Correct |
18 ms |
12712 KB |
Output is correct |
26 |
Correct |
17 ms |
12712 KB |
Output is correct |
27 |
Correct |
17 ms |
12804 KB |
Output is correct |
28 |
Correct |
10 ms |
10964 KB |
Output is correct |
29 |
Correct |
15 ms |
11484 KB |
Output is correct |
30 |
Correct |
17 ms |
11624 KB |
Output is correct |
31 |
Correct |
16 ms |
11604 KB |
Output is correct |
32 |
Correct |
14 ms |
11576 KB |
Output is correct |
33 |
Correct |
4 ms |
9016 KB |
Output is correct |
34 |
Correct |
4 ms |
9044 KB |
Output is correct |
35 |
Correct |
4 ms |
9044 KB |
Output is correct |
36 |
Correct |
5 ms |
9044 KB |
Output is correct |
37 |
Correct |
4 ms |
9044 KB |
Output is correct |
38 |
Correct |
47 ms |
31512 KB |
Output is correct |
39 |
Correct |
47 ms |
31588 KB |
Output is correct |
40 |
Correct |
43 ms |
31596 KB |
Output is correct |
41 |
Correct |
43 ms |
31524 KB |
Output is correct |
42 |
Correct |
175 ms |
54556 KB |
Output is correct |
43 |
Correct |
173 ms |
54576 KB |
Output is correct |
44 |
Correct |
177 ms |
54764 KB |
Output is correct |
45 |
Correct |
161 ms |
52060 KB |
Output is correct |
46 |
Correct |
89 ms |
30420 KB |
Output is correct |
47 |
Correct |
98 ms |
31564 KB |
Output is correct |
48 |
Correct |
146 ms |
37964 KB |
Output is correct |
49 |
Correct |
175 ms |
39972 KB |
Output is correct |
50 |
Correct |
73 ms |
25512 KB |
Output is correct |
51 |
Correct |
66 ms |
25432 KB |
Output is correct |
52 |
Correct |
179 ms |
38900 KB |
Output is correct |
53 |
Correct |
168 ms |
40016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
58288 KB |
Output is correct |
2 |
Correct |
25 ms |
44516 KB |
Output is correct |
3 |
Correct |
31 ms |
58228 KB |
Output is correct |
4 |
Correct |
5 ms |
9044 KB |
Output is correct |
5 |
Correct |
32 ms |
58196 KB |
Output is correct |
6 |
Correct |
30 ms |
58260 KB |
Output is correct |
7 |
Correct |
31 ms |
58284 KB |
Output is correct |
8 |
Correct |
30 ms |
58176 KB |
Output is correct |
9 |
Correct |
29 ms |
58156 KB |
Output is correct |
10 |
Correct |
31 ms |
58084 KB |
Output is correct |
11 |
Correct |
30 ms |
58096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9016 KB |
Output is correct |
2 |
Correct |
4 ms |
9044 KB |
Output is correct |
3 |
Correct |
4 ms |
9044 KB |
Output is correct |
4 |
Correct |
5 ms |
9044 KB |
Output is correct |
5 |
Correct |
4 ms |
9044 KB |
Output is correct |
6 |
Correct |
4 ms |
9044 KB |
Output is correct |
7 |
Correct |
628 ms |
141696 KB |
Output is correct |
8 |
Correct |
1370 ms |
276888 KB |
Output is correct |
9 |
Correct |
1414 ms |
278224 KB |
Output is correct |
10 |
Correct |
1391 ms |
278308 KB |
Output is correct |
11 |
Correct |
212 ms |
148804 KB |
Output is correct |
12 |
Correct |
532 ms |
250624 KB |
Output is correct |
13 |
Correct |
440 ms |
266464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9044 KB |
Output is correct |
2 |
Correct |
5 ms |
9172 KB |
Output is correct |
3 |
Correct |
6 ms |
9172 KB |
Output is correct |
4 |
Correct |
5 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9128 KB |
Output is correct |
6 |
Correct |
5 ms |
9132 KB |
Output is correct |
7 |
Correct |
5 ms |
9060 KB |
Output is correct |
8 |
Correct |
5 ms |
9024 KB |
Output is correct |
9 |
Correct |
5 ms |
9044 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
6 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
9044 KB |
Output is correct |
13 |
Correct |
5 ms |
9044 KB |
Output is correct |
14 |
Correct |
4 ms |
9044 KB |
Output is correct |
15 |
Correct |
5 ms |
9044 KB |
Output is correct |
16 |
Correct |
6 ms |
9044 KB |
Output is correct |
17 |
Correct |
8 ms |
9564 KB |
Output is correct |
18 |
Correct |
9 ms |
9584 KB |
Output is correct |
19 |
Correct |
7 ms |
9684 KB |
Output is correct |
20 |
Correct |
6 ms |
9408 KB |
Output is correct |
21 |
Correct |
7 ms |
9428 KB |
Output is correct |
22 |
Correct |
7 ms |
9404 KB |
Output is correct |
23 |
Correct |
7 ms |
9488 KB |
Output is correct |
24 |
Correct |
5 ms |
9300 KB |
Output is correct |
25 |
Correct |
18 ms |
12712 KB |
Output is correct |
26 |
Correct |
17 ms |
12712 KB |
Output is correct |
27 |
Correct |
17 ms |
12804 KB |
Output is correct |
28 |
Correct |
10 ms |
10964 KB |
Output is correct |
29 |
Correct |
15 ms |
11484 KB |
Output is correct |
30 |
Correct |
17 ms |
11624 KB |
Output is correct |
31 |
Correct |
16 ms |
11604 KB |
Output is correct |
32 |
Correct |
14 ms |
11576 KB |
Output is correct |
33 |
Correct |
47 ms |
31512 KB |
Output is correct |
34 |
Correct |
47 ms |
31588 KB |
Output is correct |
35 |
Correct |
43 ms |
31596 KB |
Output is correct |
36 |
Correct |
43 ms |
31524 KB |
Output is correct |
37 |
Correct |
175 ms |
54556 KB |
Output is correct |
38 |
Correct |
173 ms |
54576 KB |
Output is correct |
39 |
Correct |
177 ms |
54764 KB |
Output is correct |
40 |
Correct |
161 ms |
52060 KB |
Output is correct |
41 |
Correct |
89 ms |
30420 KB |
Output is correct |
42 |
Correct |
98 ms |
31564 KB |
Output is correct |
43 |
Correct |
146 ms |
37964 KB |
Output is correct |
44 |
Correct |
175 ms |
39972 KB |
Output is correct |
45 |
Correct |
73 ms |
25512 KB |
Output is correct |
46 |
Correct |
66 ms |
25432 KB |
Output is correct |
47 |
Correct |
179 ms |
38900 KB |
Output is correct |
48 |
Correct |
168 ms |
40016 KB |
Output is correct |
49 |
Correct |
31 ms |
58288 KB |
Output is correct |
50 |
Correct |
25 ms |
44516 KB |
Output is correct |
51 |
Correct |
31 ms |
58228 KB |
Output is correct |
52 |
Correct |
5 ms |
9044 KB |
Output is correct |
53 |
Correct |
32 ms |
58196 KB |
Output is correct |
54 |
Correct |
30 ms |
58260 KB |
Output is correct |
55 |
Correct |
31 ms |
58284 KB |
Output is correct |
56 |
Correct |
30 ms |
58176 KB |
Output is correct |
57 |
Correct |
29 ms |
58156 KB |
Output is correct |
58 |
Correct |
31 ms |
58084 KB |
Output is correct |
59 |
Correct |
30 ms |
58096 KB |
Output is correct |
60 |
Correct |
4 ms |
9044 KB |
Output is correct |
61 |
Correct |
628 ms |
141696 KB |
Output is correct |
62 |
Correct |
1370 ms |
276888 KB |
Output is correct |
63 |
Correct |
1414 ms |
278224 KB |
Output is correct |
64 |
Correct |
1391 ms |
278308 KB |
Output is correct |
65 |
Correct |
212 ms |
148804 KB |
Output is correct |
66 |
Correct |
532 ms |
250624 KB |
Output is correct |
67 |
Correct |
440 ms |
266464 KB |
Output is correct |
68 |
Correct |
4 ms |
9016 KB |
Output is correct |
69 |
Correct |
4 ms |
9044 KB |
Output is correct |
70 |
Correct |
4 ms |
9044 KB |
Output is correct |
71 |
Correct |
5 ms |
9044 KB |
Output is correct |
72 |
Correct |
4 ms |
9044 KB |
Output is correct |
73 |
Correct |
826 ms |
268064 KB |
Output is correct |
74 |
Correct |
845 ms |
268068 KB |
Output is correct |
75 |
Correct |
717 ms |
268072 KB |
Output is correct |
76 |
Correct |
753 ms |
268152 KB |
Output is correct |
77 |
Correct |
3530 ms |
561260 KB |
Output is correct |
78 |
Correct |
1936 ms |
237492 KB |
Output is correct |
79 |
Correct |
2058 ms |
256140 KB |
Output is correct |
80 |
Correct |
3495 ms |
373924 KB |
Output is correct |
81 |
Correct |
2151 ms |
225292 KB |
Output is correct |
82 |
Correct |
2586 ms |
289164 KB |
Output is correct |
83 |
Correct |
3858 ms |
356560 KB |
Output is correct |
84 |
Correct |
2234 ms |
224784 KB |
Output is correct |
85 |
Correct |
4221 ms |
356040 KB |
Output is correct |
86 |
Correct |
3692 ms |
346400 KB |
Output is correct |
87 |
Correct |
2086 ms |
341028 KB |
Output is correct |
88 |
Correct |
3579 ms |
548560 KB |
Output is correct |
89 |
Correct |
3647 ms |
549024 KB |
Output is correct |
90 |
Correct |
3642 ms |
548976 KB |
Output is correct |