#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long count_rectangles (std::vector<std::vector<int> > a) {
ll n = a.size ();
ll m = a[0].size ();
vector < vector < vector < ll > > >
ra (n, vector < vector < ll > > (m, vector < ll > (m))),
ca (m, vector < vector < ll > > (n, vector < ll > (n)));
for (ll k = 0; k < n; ++k)
for (ll i = 0; i < m; ++i)
{
int mx = 0;
for (ll j = i + 2; j < m; ++j)
{
mx = max (mx, a[k][j - 1]);
if (mx < a[k][i] && mx < a[k][j]) ra[k][i + 1][j - 1] = 1;
}
}
for (ll k = 0; k < m; ++k)
for (ll i = 0; i < n; ++i)
{
int mx = 0;
for (ll j = i + 2; j < n; ++j)
{
mx = max (mx, a[j - 1][k]);
if (mx < a[i][k] && mx < a[j][k]) ca[k][i + 1][j - 1] = 1;
}
}
for (ll i = 1; i < n; ++i)
for (ll j = 0; j < m; ++j)
for (ll k = 0; k < m; ++k)
ra[i][j][k] += ra[i - 1][j][k];
for (ll i = 1; i < m; ++i)
for (ll j = 0; j < n; ++j)
for (ll k = 0; k < n; ++k)
ca[i][j][k] += ca[i - 1][j][k];
auto alp = [&] (auto &x, int a, int b, int c, int d)
{
return (x[d][a][b] - (c ? x[c - 1][a][b] : 0)) == d - c + 1;
};
int c = 0;
for (ll i1 = 0; i1 < n; ++i1)
for (ll i2 = i1; i2 < n; ++i2)
for (ll j1 = 0; j1 < m; ++j1)
for (ll j2 = j1; j2 < m; ++j2)
if (alp (ca, i1, i2, j1, j2) && alp (ra, j1, j2, i1, i2))
++c;
return c;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
952 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
432 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
504 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
952 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
432 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
504 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
25 ms |
9048 KB |
Output is correct |
23 |
Correct |
27 ms |
9052 KB |
Output is correct |
24 |
Correct |
31 ms |
9100 KB |
Output is correct |
25 |
Correct |
25 ms |
9052 KB |
Output is correct |
26 |
Correct |
24 ms |
8796 KB |
Output is correct |
27 |
Correct |
32 ms |
8792 KB |
Output is correct |
28 |
Correct |
25 ms |
9084 KB |
Output is correct |
29 |
Correct |
7 ms |
3676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
952 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
432 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
504 KB |
Output is correct |
17 |
Correct |
25 ms |
9048 KB |
Output is correct |
18 |
Correct |
27 ms |
9052 KB |
Output is correct |
19 |
Correct |
31 ms |
9100 KB |
Output is correct |
20 |
Correct |
25 ms |
9052 KB |
Output is correct |
21 |
Correct |
24 ms |
8796 KB |
Output is correct |
22 |
Correct |
32 ms |
8792 KB |
Output is correct |
23 |
Correct |
25 ms |
9084 KB |
Output is correct |
24 |
Correct |
7 ms |
3676 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
856 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
826 ms |
129672 KB |
Output is correct |
31 |
Correct |
847 ms |
129672 KB |
Output is correct |
32 |
Correct |
807 ms |
129752 KB |
Output is correct |
33 |
Correct |
851 ms |
129524 KB |
Output is correct |
34 |
Correct |
845 ms |
129592 KB |
Output is correct |
35 |
Correct |
857 ms |
129872 KB |
Output is correct |
36 |
Correct |
850 ms |
129716 KB |
Output is correct |
37 |
Correct |
869 ms |
126800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
952 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
432 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
504 KB |
Output is correct |
17 |
Correct |
25 ms |
9048 KB |
Output is correct |
18 |
Correct |
27 ms |
9052 KB |
Output is correct |
19 |
Correct |
31 ms |
9100 KB |
Output is correct |
20 |
Correct |
25 ms |
9052 KB |
Output is correct |
21 |
Correct |
24 ms |
8796 KB |
Output is correct |
22 |
Correct |
32 ms |
8792 KB |
Output is correct |
23 |
Correct |
25 ms |
9084 KB |
Output is correct |
24 |
Correct |
7 ms |
3676 KB |
Output is correct |
25 |
Correct |
826 ms |
129672 KB |
Output is correct |
26 |
Correct |
847 ms |
129672 KB |
Output is correct |
27 |
Correct |
807 ms |
129752 KB |
Output is correct |
28 |
Correct |
851 ms |
129524 KB |
Output is correct |
29 |
Correct |
845 ms |
129592 KB |
Output is correct |
30 |
Correct |
857 ms |
129872 KB |
Output is correct |
31 |
Correct |
850 ms |
129716 KB |
Output is correct |
32 |
Correct |
869 ms |
126800 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
856 KB |
Output is correct |
36 |
Correct |
1 ms |
604 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Runtime error |
856 ms |
1048576 KB |
Execution killed with signal 9 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
196392 KB |
Output is correct |
2 |
Correct |
128 ms |
141972 KB |
Output is correct |
3 |
Correct |
146 ms |
196596 KB |
Output is correct |
4 |
Correct |
1 ms |
428 KB |
Output is correct |
5 |
Correct |
148 ms |
196636 KB |
Output is correct |
6 |
Correct |
150 ms |
196792 KB |
Output is correct |
7 |
Correct |
141 ms |
196432 KB |
Output is correct |
8 |
Correct |
142 ms |
196468 KB |
Output is correct |
9 |
Correct |
142 ms |
196456 KB |
Output is correct |
10 |
Correct |
51 ms |
98384 KB |
Output is correct |
11 |
Correct |
92 ms |
147536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
856 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Runtime error |
485 ms |
1048576 KB |
Execution killed with signal 9 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
860 KB |
Output is correct |
4 |
Correct |
1 ms |
860 KB |
Output is correct |
5 |
Correct |
1 ms |
860 KB |
Output is correct |
6 |
Correct |
1 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
952 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
432 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
504 KB |
Output is correct |
17 |
Correct |
25 ms |
9048 KB |
Output is correct |
18 |
Correct |
27 ms |
9052 KB |
Output is correct |
19 |
Correct |
31 ms |
9100 KB |
Output is correct |
20 |
Correct |
25 ms |
9052 KB |
Output is correct |
21 |
Correct |
24 ms |
8796 KB |
Output is correct |
22 |
Correct |
32 ms |
8792 KB |
Output is correct |
23 |
Correct |
25 ms |
9084 KB |
Output is correct |
24 |
Correct |
7 ms |
3676 KB |
Output is correct |
25 |
Correct |
826 ms |
129672 KB |
Output is correct |
26 |
Correct |
847 ms |
129672 KB |
Output is correct |
27 |
Correct |
807 ms |
129752 KB |
Output is correct |
28 |
Correct |
851 ms |
129524 KB |
Output is correct |
29 |
Correct |
845 ms |
129592 KB |
Output is correct |
30 |
Correct |
857 ms |
129872 KB |
Output is correct |
31 |
Correct |
850 ms |
129716 KB |
Output is correct |
32 |
Correct |
869 ms |
126800 KB |
Output is correct |
33 |
Runtime error |
856 ms |
1048576 KB |
Execution killed with signal 9 |
34 |
Halted |
0 ms |
0 KB |
- |