#include <bits/stdc++.h>
using namespace std;
const int N = 2500;
short l[N][N], r[N][N], u[N][N], d[N][N];
short lu[N][N], ru[N][N], ul[N][N], dl[N][N];
short mono[N];
array<short, 4> rects[8 * N * N];
long long count_rectangles(vector<vector<int>> a) {
short n = a.size(), m = a[0].size();
for (short i = 0; i < n; ++i) {
for (short j = 0; j < m; ++j) {
l[i][j] = r[i][j] = u[i][j] = d[i][j] = -1;
}
}
for (short i = 0; i < n; ++i) {
short top = -1;
for (short j = 0; j < m; ++j) {
while (top >= 0 && a[i][mono[top]] < a[i][j]) {
short k = mono[top--];
if (k + 1 <= j - 1) {
r[i][k + 1] = j - 1;
}
}
if (top >= 0) {
short k = mono[top];
top -= a[i][k] == a[i][j];
if (k + 1 <= j - 1) {
l[i][j - 1] = k + 1;
}
}
mono[++top] = j;
}
}
for (short i = 0; i < m; ++i) {
short top = -1;
for (short j = 0; j < n; ++j) {
while (top >= 0 && a[mono[top]][i] < a[j][i]) {
short k = mono[top--];
if (k + 1 <= j - 1) {
d[k + 1][i] = j - 1;
}
}
if (top >= 0) {
short k = mono[top];
top -= a[k][i] == a[j][i];
if (k + 1 <= j - 1) {
u[j - 1][i] = k + 1;
}
}
mono[++top] = j;
}
}
for (short i = 0; i < n; ++i) {
for (short j = 0; j < m; ++j) {
if (l[i][j] != -1) {
if (i > 0 && l[i][j] == l[i - 1][j]) {
lu[i][j] = lu[i - 1][j];
} else if (i > 0 && r[i - 1][l[i][j]] == j) {
lu[i][j] = ru[i - 1][l[i][j]];
} else {
lu[i][j] = i;
}
}
if (r[i][j] != -1) {
if (i > 0 && r[i][j] == r[i - 1][j]) {
ru[i][j] = ru[i - 1][j];
} else if (i > 0 && l[i - 1][r[i][j]] == j) {
ru[i][j] = lu[i - 1][r[i][j]];
} else {
ru[i][j] = i;
}
}
}
}
for (short j = 0; j < m; ++j) {
for (short i = 0; i < n; ++i) {
if (u[i][j] != -1) {
if (j > 0 && u[i][j] == u[i][j - 1]) {
ul[i][j] = ul[i][j - 1];
} else if (j > 0 && d[u[i][j]][j - 1] == i) {
ul[i][j] = dl[u[i][j]][j - 1];
} else {
ul[i][j] = j;
}
}
if (d[i][j] != -1) {
if (j > 0 && d[i][j] == d[i][j - 1]) {
dl[i][j] = dl[i][j - 1];
} else if (j > 0 && u[d[i][j]][j - 1] == i) {
dl[i][j] = ul[d[i][j]][j - 1];
} else {
dl[i][j] = j;
}
}
}
}
int ans = 0;
for (short i1 = 0; i1 < n; ++i1) {
for (short j1 = 0; j1 < m; ++j1) {
for (auto i2 : {u[i1][j1], d[i1][j1]}) {
if (i2 == -1) {
continue;
}
for (auto i : {i1, i2}) {
for (auto j2 : {l[i][j1], r[i][j1]}) {
if (j2 == -1) {
continue;
}
short iu = min(i1, i2), id = max(i1, i2);
short jl = min(j1, j2), jr = max(j1, j2);
if (!(l[id][jr] == jl && lu[id][jr] <= iu) && !(r[id][jl] == jr && ru[id][jl] <= iu)) {
continue;
}
if (!(u[id][jr] == iu && ul[id][jr] <= jl) && !(d[iu][jr] == id && dl[iu][jr] <= jl)) {
continue;
}
rects[ans++] = {iu, id, jl, jr};
}
}
}
}
}
sort(rects, rects + ans);
return unique(rects, rects + ans) - rects;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
1 ms |
1100 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
972 KB |
Output is correct |
20 |
Correct |
1 ms |
716 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
1 ms |
1100 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
972 KB |
Output is correct |
20 |
Correct |
1 ms |
716 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
4 ms |
2764 KB |
Output is correct |
23 |
Correct |
4 ms |
2764 KB |
Output is correct |
24 |
Correct |
4 ms |
2764 KB |
Output is correct |
25 |
Correct |
3 ms |
2892 KB |
Output is correct |
26 |
Correct |
3 ms |
3020 KB |
Output is correct |
27 |
Correct |
4 ms |
3052 KB |
Output is correct |
28 |
Correct |
3 ms |
3020 KB |
Output is correct |
29 |
Correct |
3 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
1 ms |
1100 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
2764 KB |
Output is correct |
18 |
Correct |
4 ms |
2764 KB |
Output is correct |
19 |
Correct |
4 ms |
2764 KB |
Output is correct |
20 |
Correct |
3 ms |
2892 KB |
Output is correct |
21 |
Correct |
3 ms |
3020 KB |
Output is correct |
22 |
Correct |
4 ms |
3052 KB |
Output is correct |
23 |
Correct |
3 ms |
3020 KB |
Output is correct |
24 |
Correct |
3 ms |
2892 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
972 KB |
Output is correct |
28 |
Correct |
1 ms |
716 KB |
Output is correct |
29 |
Correct |
1 ms |
460 KB |
Output is correct |
30 |
Correct |
17 ms |
7232 KB |
Output is correct |
31 |
Correct |
20 ms |
7244 KB |
Output is correct |
32 |
Correct |
17 ms |
7244 KB |
Output is correct |
33 |
Correct |
7 ms |
7628 KB |
Output is correct |
34 |
Correct |
12 ms |
7756 KB |
Output is correct |
35 |
Correct |
13 ms |
7768 KB |
Output is correct |
36 |
Correct |
12 ms |
7856 KB |
Output is correct |
37 |
Correct |
13 ms |
7756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
1 ms |
1100 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
2764 KB |
Output is correct |
18 |
Correct |
4 ms |
2764 KB |
Output is correct |
19 |
Correct |
4 ms |
2764 KB |
Output is correct |
20 |
Correct |
3 ms |
2892 KB |
Output is correct |
21 |
Correct |
3 ms |
3020 KB |
Output is correct |
22 |
Correct |
4 ms |
3052 KB |
Output is correct |
23 |
Correct |
3 ms |
3020 KB |
Output is correct |
24 |
Correct |
3 ms |
2892 KB |
Output is correct |
25 |
Correct |
17 ms |
7232 KB |
Output is correct |
26 |
Correct |
20 ms |
7244 KB |
Output is correct |
27 |
Correct |
17 ms |
7244 KB |
Output is correct |
28 |
Correct |
7 ms |
7628 KB |
Output is correct |
29 |
Correct |
12 ms |
7756 KB |
Output is correct |
30 |
Correct |
13 ms |
7768 KB |
Output is correct |
31 |
Correct |
12 ms |
7856 KB |
Output is correct |
32 |
Correct |
13 ms |
7756 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
972 KB |
Output is correct |
36 |
Correct |
1 ms |
716 KB |
Output is correct |
37 |
Correct |
1 ms |
460 KB |
Output is correct |
38 |
Correct |
51 ms |
24248 KB |
Output is correct |
39 |
Correct |
50 ms |
24248 KB |
Output is correct |
40 |
Correct |
48 ms |
24260 KB |
Output is correct |
41 |
Correct |
48 ms |
24260 KB |
Output is correct |
42 |
Correct |
247 ms |
35108 KB |
Output is correct |
43 |
Correct |
229 ms |
35140 KB |
Output is correct |
44 |
Correct |
218 ms |
35188 KB |
Output is correct |
45 |
Correct |
208 ms |
32892 KB |
Output is correct |
46 |
Correct |
55 ms |
25076 KB |
Output is correct |
47 |
Correct |
78 ms |
32268 KB |
Output is correct |
48 |
Correct |
136 ms |
34116 KB |
Output is correct |
49 |
Correct |
142 ms |
34116 KB |
Output is correct |
50 |
Correct |
71 ms |
29732 KB |
Output is correct |
51 |
Correct |
63 ms |
17216 KB |
Output is correct |
52 |
Correct |
130 ms |
34244 KB |
Output is correct |
53 |
Correct |
137 ms |
34184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
2 ms |
464 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
972 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
299 ms |
60844 KB |
Output is correct |
8 |
Correct |
690 ms |
126068 KB |
Output is correct |
9 |
Correct |
668 ms |
126744 KB |
Output is correct |
10 |
Correct |
679 ms |
126616 KB |
Output is correct |
11 |
Correct |
185 ms |
48708 KB |
Output is correct |
12 |
Correct |
447 ms |
95268 KB |
Output is correct |
13 |
Correct |
482 ms |
98324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
1 ms |
1100 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
1228 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1316 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
2764 KB |
Output is correct |
18 |
Correct |
4 ms |
2764 KB |
Output is correct |
19 |
Correct |
4 ms |
2764 KB |
Output is correct |
20 |
Correct |
3 ms |
2892 KB |
Output is correct |
21 |
Correct |
3 ms |
3020 KB |
Output is correct |
22 |
Correct |
4 ms |
3052 KB |
Output is correct |
23 |
Correct |
3 ms |
3020 KB |
Output is correct |
24 |
Correct |
3 ms |
2892 KB |
Output is correct |
25 |
Correct |
17 ms |
7232 KB |
Output is correct |
26 |
Correct |
20 ms |
7244 KB |
Output is correct |
27 |
Correct |
17 ms |
7244 KB |
Output is correct |
28 |
Correct |
7 ms |
7628 KB |
Output is correct |
29 |
Correct |
12 ms |
7756 KB |
Output is correct |
30 |
Correct |
13 ms |
7768 KB |
Output is correct |
31 |
Correct |
12 ms |
7856 KB |
Output is correct |
32 |
Correct |
13 ms |
7756 KB |
Output is correct |
33 |
Correct |
51 ms |
24248 KB |
Output is correct |
34 |
Correct |
50 ms |
24248 KB |
Output is correct |
35 |
Correct |
48 ms |
24260 KB |
Output is correct |
36 |
Correct |
48 ms |
24260 KB |
Output is correct |
37 |
Correct |
247 ms |
35108 KB |
Output is correct |
38 |
Correct |
229 ms |
35140 KB |
Output is correct |
39 |
Correct |
218 ms |
35188 KB |
Output is correct |
40 |
Correct |
208 ms |
32892 KB |
Output is correct |
41 |
Correct |
55 ms |
25076 KB |
Output is correct |
42 |
Correct |
78 ms |
32268 KB |
Output is correct |
43 |
Correct |
136 ms |
34116 KB |
Output is correct |
44 |
Correct |
142 ms |
34116 KB |
Output is correct |
45 |
Correct |
71 ms |
29732 KB |
Output is correct |
46 |
Correct |
63 ms |
17216 KB |
Output is correct |
47 |
Correct |
130 ms |
34244 KB |
Output is correct |
48 |
Correct |
137 ms |
34184 KB |
Output is correct |
49 |
Correct |
2 ms |
460 KB |
Output is correct |
50 |
Correct |
2 ms |
460 KB |
Output is correct |
51 |
Correct |
1 ms |
460 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
2 ms |
460 KB |
Output is correct |
54 |
Correct |
2 ms |
460 KB |
Output is correct |
55 |
Correct |
2 ms |
460 KB |
Output is correct |
56 |
Correct |
2 ms |
460 KB |
Output is correct |
57 |
Correct |
2 ms |
464 KB |
Output is correct |
58 |
Correct |
1 ms |
332 KB |
Output is correct |
59 |
Correct |
1 ms |
332 KB |
Output is correct |
60 |
Correct |
1 ms |
460 KB |
Output is correct |
61 |
Correct |
299 ms |
60844 KB |
Output is correct |
62 |
Correct |
690 ms |
126068 KB |
Output is correct |
63 |
Correct |
668 ms |
126744 KB |
Output is correct |
64 |
Correct |
679 ms |
126616 KB |
Output is correct |
65 |
Correct |
185 ms |
48708 KB |
Output is correct |
66 |
Correct |
447 ms |
95268 KB |
Output is correct |
67 |
Correct |
482 ms |
98324 KB |
Output is correct |
68 |
Correct |
1 ms |
332 KB |
Output is correct |
69 |
Correct |
1 ms |
332 KB |
Output is correct |
70 |
Correct |
1 ms |
972 KB |
Output is correct |
71 |
Correct |
1 ms |
716 KB |
Output is correct |
72 |
Correct |
1 ms |
460 KB |
Output is correct |
73 |
Correct |
768 ms |
122520 KB |
Output is correct |
74 |
Correct |
764 ms |
122372 KB |
Output is correct |
75 |
Correct |
742 ms |
122504 KB |
Output is correct |
76 |
Correct |
725 ms |
122436 KB |
Output is correct |
77 |
Correct |
3297 ms |
230468 KB |
Output is correct |
78 |
Correct |
1038 ms |
108532 KB |
Output is correct |
79 |
Correct |
1047 ms |
172472 KB |
Output is correct |
80 |
Correct |
1802 ms |
203524 KB |
Output is correct |
81 |
Correct |
1096 ms |
137528 KB |
Output is correct |
82 |
Correct |
1390 ms |
202652 KB |
Output is correct |
83 |
Correct |
1848 ms |
228732 KB |
Output is correct |
84 |
Correct |
1086 ms |
130008 KB |
Output is correct |
85 |
Correct |
1831 ms |
228816 KB |
Output is correct |
86 |
Correct |
1843 ms |
222528 KB |
Output is correct |
87 |
Correct |
1898 ms |
200732 KB |
Output is correct |
88 |
Correct |
3291 ms |
278308 KB |
Output is correct |
89 |
Correct |
3376 ms |
278412 KB |
Output is correct |
90 |
Correct |
3352 ms |
278492 KB |
Output is correct |