#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax = 2505;
int go_up[Nmax][Nmax], go_down[Nmax][Nmax], go_left[Nmax][Nmax], go_right[Nmax][Nmax], h[Nmax][Nmax];
int dp_up[Nmax][Nmax], dp_down[Nmax][Nmax], dp_left[Nmax][Nmax], dp_right[Nmax][Nmax];
int n, m;
vector<int> pos[Nmax];
static void compute(vector<int> &v, vector<int> &go)
{
go.resize(v.size());
int i, nr = 0;
vector<int> st(v.size() + 1);
st[0] = -1;
for(i=0; i<v.size(); ++i)
{
while(nr && v[i] > v[st[nr]]) --nr;
go[i] = st[nr];
st[++nr] = i;
}
}
static void prec()
{
vector<int> aux, ans;
int i, j;
for(i=0; i<n; ++i)
{
aux.clear();
for(j=0; j<m; ++j) aux.push_back(h[i][j]);
compute(aux, ans);
for(j=0; j<m; ++j)
go_left[i][j] = ans[j];
reverse(aux.begin(), aux.end());
compute(aux, ans);
for(j=0; j<m; ++j)
go_right[i][j] = m-1-ans[m-j-1];
}
for(j=0; j<m; ++j)
{
aux.clear();
for(i=0; i<n; ++i) aux.push_back(h[i][j]);
compute(aux, ans);
for(i=0; i<n; ++i)
go_up[i][j] = ans[i];
reverse(aux.begin(), aux.end());
compute(aux, ans);
for(i=0; i<n; ++i)
go_down[i][j] = n-1-ans[n-i-1];
}
}
static void prec2()
{
int i, j;
for(j=m-1; j>=0; --j)
for(i=n-1; i>=0; --i)
{
if(j<m-1 && go_down[i][j+1] == go_down[i][j])
dp_down[i][j] = 1 + dp_down[i][j+1];
else if(j<m-1 && go_up[go_down[i][j]][j+1] == i) dp_down[i][j] = 1 + dp_up[go_down[i][j]][j+1];
else dp_down[i][j] = 1;
///
if(j<m-1 && go_up[i][j+1] == go_up[i][j])
dp_up[i][j] = 1 + dp_up[i][j+1];
else if(j<m-1 && go_down[go_up[i][j]][j+1] == i) dp_up[i][j] = 1 + dp_down[go_up[i][j]][j+1];
else dp_up[i][j] = 1;
}
for(i=n-1; i>=0; --i)
for(j=m-1; j>=0; --j)
{
///
if(i<n-1 && go_right[i+1][j] == go_right[i][j])
dp_right[i][j] = 1 + dp_right[i+1][j];
else if(i<n-1 && go_left[i+1][go_right[i][j]] == j) dp_right[i][j] = 1 + dp_left[i+1][go_right[i][j]];
else dp_right[i][j] = 1;
///
if(i<n-1 && go_left[i+1][j] == go_left[i][j])
dp_left[i][j] = 1 + dp_left[i+1][j];
else if(i<n-1 && go_right[i+1][go_left[i][j]] == j) dp_left[i][j] = 1 + dp_right[i+1][go_left[i][j]];
else dp_left[i][j] = 1;
}
}
static bool check(int x, int y, int n, int m)
{
if(!n || !m) return 0;
// cerr << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';
/// coltul stanga-sus in (x, y), dimensiune (n, m)
bool ok = 1;
if(go_down[x-1][y] == x+n)
ok &= (dp_down[x-1][y] >= m);
else if(go_up[x+n][y] == x-1) ok &= (dp_up[x+n][y] >= m);
else ok = 0;
if(go_right[x][y-1] == y+m)
ok &= (dp_right[x][y-1] >= n);
else if(go_left[x][y+m] == y-1) ok &= (dp_left[x][y+m] >= n);
else ok = 0;
// cerr << "answer: " << (int) ok << '\n';
// if(ok) cerr << "# " << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';
return ok;
}
ll solve()
{
int i, j;
int ans = 0;
for(i=1; i<n-1; ++i)
{
for(j=0; j<=m; ++j) pos[j].clear(); /// pos[j].shrink_to_fit();
for(j=0; j<m; ++j)
{
if(go_right[i][j] != m)
pos[j+1].push_back(go_right[i][j] - j - 1);
if(go_left[i][j] != -1 && h[i][j] != h[i][go_left[i][j]])
pos[go_left[i][j] + 1].push_back(j - go_left[i][j] - 1);
}
for(j=1; j<m-1; ++j)
{
if(go_down[i-1][j] == n) continue;
int N;
N = go_down[i-1][j] - i;
for(auto M : pos[j])
ans += check(i, j, N, M);
}
for(j=m-2; j>=1; --j)
{
if(go_up[i+1][j] == -1) continue;
if(h[i+1][j] == h[go_up[i+1][j]][j]) continue;
int N;
N = i - go_up[i+1][j];
for(auto M : pos[j])
ans += check(i-N+1, j, N, M);
}
}
return ans;
}
ll count_rectangles(vector<vector<int>> _h)
{
n = _h.size();
m = _h[0].size();
int i, j;
for(i=0; i<n; ++i)
for(j=0; j<m; ++j)
h[i][j] = _h[i][j];
prec();
prec2();
return solve();
}
Compilation message
rect.cpp: In function 'void compute(std::vector<int>&, std::vector<int>&)':
rect.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<v.size(); ++i)
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
1528 KB |
Output is correct |
4 |
Correct |
3 ms |
1528 KB |
Output is correct |
5 |
Correct |
3 ms |
1528 KB |
Output is correct |
6 |
Correct |
3 ms |
1528 KB |
Output is correct |
7 |
Correct |
3 ms |
1528 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1576 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
760 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
508 KB |
Output is correct |
19 |
Correct |
3 ms |
1528 KB |
Output is correct |
20 |
Correct |
3 ms |
1528 KB |
Output is correct |
21 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
1528 KB |
Output is correct |
4 |
Correct |
3 ms |
1528 KB |
Output is correct |
5 |
Correct |
3 ms |
1528 KB |
Output is correct |
6 |
Correct |
3 ms |
1528 KB |
Output is correct |
7 |
Correct |
3 ms |
1528 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1576 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
760 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
3580 KB |
Output is correct |
18 |
Correct |
6 ms |
3704 KB |
Output is correct |
19 |
Correct |
5 ms |
3576 KB |
Output is correct |
20 |
Correct |
6 ms |
3576 KB |
Output is correct |
21 |
Correct |
6 ms |
3604 KB |
Output is correct |
22 |
Correct |
6 ms |
3576 KB |
Output is correct |
23 |
Correct |
6 ms |
3672 KB |
Output is correct |
24 |
Correct |
5 ms |
3448 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
508 KB |
Output is correct |
27 |
Correct |
3 ms |
1528 KB |
Output is correct |
28 |
Correct |
3 ms |
1528 KB |
Output is correct |
29 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
1528 KB |
Output is correct |
4 |
Correct |
3 ms |
1528 KB |
Output is correct |
5 |
Correct |
3 ms |
1528 KB |
Output is correct |
6 |
Correct |
3 ms |
1528 KB |
Output is correct |
7 |
Correct |
3 ms |
1528 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1576 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
760 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
3580 KB |
Output is correct |
18 |
Correct |
6 ms |
3704 KB |
Output is correct |
19 |
Correct |
5 ms |
3576 KB |
Output is correct |
20 |
Correct |
6 ms |
3576 KB |
Output is correct |
21 |
Correct |
6 ms |
3604 KB |
Output is correct |
22 |
Correct |
6 ms |
3576 KB |
Output is correct |
23 |
Correct |
6 ms |
3672 KB |
Output is correct |
24 |
Correct |
5 ms |
3448 KB |
Output is correct |
25 |
Correct |
14 ms |
9592 KB |
Output is correct |
26 |
Correct |
14 ms |
9596 KB |
Output is correct |
27 |
Correct |
15 ms |
9720 KB |
Output is correct |
28 |
Correct |
15 ms |
9464 KB |
Output is correct |
29 |
Correct |
17 ms |
9464 KB |
Output is correct |
30 |
Correct |
18 ms |
9720 KB |
Output is correct |
31 |
Correct |
18 ms |
9720 KB |
Output is correct |
32 |
Correct |
17 ms |
9592 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
508 KB |
Output is correct |
35 |
Correct |
3 ms |
1528 KB |
Output is correct |
36 |
Correct |
3 ms |
1528 KB |
Output is correct |
37 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
1528 KB |
Output is correct |
4 |
Correct |
3 ms |
1528 KB |
Output is correct |
5 |
Correct |
3 ms |
1528 KB |
Output is correct |
6 |
Correct |
3 ms |
1528 KB |
Output is correct |
7 |
Correct |
3 ms |
1528 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1576 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
760 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
3580 KB |
Output is correct |
18 |
Correct |
6 ms |
3704 KB |
Output is correct |
19 |
Correct |
5 ms |
3576 KB |
Output is correct |
20 |
Correct |
6 ms |
3576 KB |
Output is correct |
21 |
Correct |
6 ms |
3604 KB |
Output is correct |
22 |
Correct |
6 ms |
3576 KB |
Output is correct |
23 |
Correct |
6 ms |
3672 KB |
Output is correct |
24 |
Correct |
5 ms |
3448 KB |
Output is correct |
25 |
Correct |
14 ms |
9592 KB |
Output is correct |
26 |
Correct |
14 ms |
9596 KB |
Output is correct |
27 |
Correct |
15 ms |
9720 KB |
Output is correct |
28 |
Correct |
15 ms |
9464 KB |
Output is correct |
29 |
Correct |
17 ms |
9464 KB |
Output is correct |
30 |
Correct |
18 ms |
9720 KB |
Output is correct |
31 |
Correct |
18 ms |
9720 KB |
Output is correct |
32 |
Correct |
17 ms |
9592 KB |
Output is correct |
33 |
Correct |
113 ms |
49968 KB |
Output is correct |
34 |
Correct |
116 ms |
51408 KB |
Output is correct |
35 |
Correct |
108 ms |
49912 KB |
Output is correct |
36 |
Correct |
114 ms |
51448 KB |
Output is correct |
37 |
Correct |
124 ms |
50040 KB |
Output is correct |
38 |
Correct |
118 ms |
50176 KB |
Output is correct |
39 |
Correct |
118 ms |
50404 KB |
Output is correct |
40 |
Correct |
110 ms |
47224 KB |
Output is correct |
41 |
Correct |
124 ms |
47836 KB |
Output is correct |
42 |
Correct |
136 ms |
47812 KB |
Output is correct |
43 |
Correct |
162 ms |
48816 KB |
Output is correct |
44 |
Correct |
169 ms |
50552 KB |
Output is correct |
45 |
Correct |
96 ms |
38292 KB |
Output is correct |
46 |
Correct |
74 ms |
25592 KB |
Output is correct |
47 |
Correct |
159 ms |
49688 KB |
Output is correct |
48 |
Correct |
164 ms |
50628 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
508 KB |
Output is correct |
51 |
Correct |
3 ms |
1528 KB |
Output is correct |
52 |
Correct |
3 ms |
1528 KB |
Output is correct |
53 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
888 KB |
Output is correct |
2 |
Correct |
3 ms |
888 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
4 ms |
888 KB |
Output is correct |
6 |
Correct |
4 ms |
888 KB |
Output is correct |
7 |
Correct |
4 ms |
888 KB |
Output is correct |
8 |
Correct |
4 ms |
888 KB |
Output is correct |
9 |
Correct |
4 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
658 ms |
137492 KB |
Output is correct |
3 |
Correct |
1523 ms |
273524 KB |
Output is correct |
4 |
Correct |
1487 ms |
282744 KB |
Output is correct |
5 |
Correct |
1485 ms |
281092 KB |
Output is correct |
6 |
Correct |
538 ms |
139804 KB |
Output is correct |
7 |
Correct |
1237 ms |
278684 KB |
Output is correct |
8 |
Correct |
1132 ms |
282616 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
508 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1528 KB |
Output is correct |
13 |
Correct |
3 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
3 ms |
1528 KB |
Output is correct |
4 |
Correct |
3 ms |
1528 KB |
Output is correct |
5 |
Correct |
3 ms |
1528 KB |
Output is correct |
6 |
Correct |
3 ms |
1528 KB |
Output is correct |
7 |
Correct |
3 ms |
1528 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
3 ms |
1528 KB |
Output is correct |
12 |
Correct |
3 ms |
1576 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
760 KB |
Output is correct |
15 |
Correct |
2 ms |
760 KB |
Output is correct |
16 |
Correct |
2 ms |
508 KB |
Output is correct |
17 |
Correct |
6 ms |
3580 KB |
Output is correct |
18 |
Correct |
6 ms |
3704 KB |
Output is correct |
19 |
Correct |
5 ms |
3576 KB |
Output is correct |
20 |
Correct |
6 ms |
3576 KB |
Output is correct |
21 |
Correct |
6 ms |
3604 KB |
Output is correct |
22 |
Correct |
6 ms |
3576 KB |
Output is correct |
23 |
Correct |
6 ms |
3672 KB |
Output is correct |
24 |
Correct |
5 ms |
3448 KB |
Output is correct |
25 |
Correct |
14 ms |
9592 KB |
Output is correct |
26 |
Correct |
14 ms |
9596 KB |
Output is correct |
27 |
Correct |
15 ms |
9720 KB |
Output is correct |
28 |
Correct |
15 ms |
9464 KB |
Output is correct |
29 |
Correct |
17 ms |
9464 KB |
Output is correct |
30 |
Correct |
18 ms |
9720 KB |
Output is correct |
31 |
Correct |
18 ms |
9720 KB |
Output is correct |
32 |
Correct |
17 ms |
9592 KB |
Output is correct |
33 |
Correct |
113 ms |
49968 KB |
Output is correct |
34 |
Correct |
116 ms |
51408 KB |
Output is correct |
35 |
Correct |
108 ms |
49912 KB |
Output is correct |
36 |
Correct |
114 ms |
51448 KB |
Output is correct |
37 |
Correct |
124 ms |
50040 KB |
Output is correct |
38 |
Correct |
118 ms |
50176 KB |
Output is correct |
39 |
Correct |
118 ms |
50404 KB |
Output is correct |
40 |
Correct |
110 ms |
47224 KB |
Output is correct |
41 |
Correct |
124 ms |
47836 KB |
Output is correct |
42 |
Correct |
136 ms |
47812 KB |
Output is correct |
43 |
Correct |
162 ms |
48816 KB |
Output is correct |
44 |
Correct |
169 ms |
50552 KB |
Output is correct |
45 |
Correct |
96 ms |
38292 KB |
Output is correct |
46 |
Correct |
74 ms |
25592 KB |
Output is correct |
47 |
Correct |
159 ms |
49688 KB |
Output is correct |
48 |
Correct |
164 ms |
50628 KB |
Output is correct |
49 |
Correct |
3 ms |
888 KB |
Output is correct |
50 |
Correct |
3 ms |
888 KB |
Output is correct |
51 |
Correct |
3 ms |
888 KB |
Output is correct |
52 |
Correct |
2 ms |
504 KB |
Output is correct |
53 |
Correct |
4 ms |
888 KB |
Output is correct |
54 |
Correct |
4 ms |
888 KB |
Output is correct |
55 |
Correct |
4 ms |
888 KB |
Output is correct |
56 |
Correct |
4 ms |
888 KB |
Output is correct |
57 |
Correct |
4 ms |
888 KB |
Output is correct |
58 |
Correct |
3 ms |
632 KB |
Output is correct |
59 |
Correct |
3 ms |
760 KB |
Output is correct |
60 |
Correct |
2 ms |
760 KB |
Output is correct |
61 |
Correct |
658 ms |
137492 KB |
Output is correct |
62 |
Correct |
1523 ms |
273524 KB |
Output is correct |
63 |
Correct |
1487 ms |
282744 KB |
Output is correct |
64 |
Correct |
1485 ms |
281092 KB |
Output is correct |
65 |
Correct |
538 ms |
139804 KB |
Output is correct |
66 |
Correct |
1237 ms |
278684 KB |
Output is correct |
67 |
Correct |
1132 ms |
282616 KB |
Output is correct |
68 |
Correct |
1287 ms |
317236 KB |
Output is correct |
69 |
Correct |
1390 ms |
333576 KB |
Output is correct |
70 |
Correct |
1323 ms |
317052 KB |
Output is correct |
71 |
Correct |
1514 ms |
290172 KB |
Output is correct |
72 |
Correct |
1392 ms |
302296 KB |
Output is correct |
73 |
Correct |
1203 ms |
176376 KB |
Output is correct |
74 |
Correct |
1353 ms |
274440 KB |
Output is correct |
75 |
Correct |
1999 ms |
270628 KB |
Output is correct |
76 |
Correct |
1272 ms |
191356 KB |
Output is correct |
77 |
Correct |
1750 ms |
280504 KB |
Output is correct |
78 |
Correct |
2122 ms |
291932 KB |
Output is correct |
79 |
Correct |
1186 ms |
184056 KB |
Output is correct |
80 |
Correct |
2039 ms |
270676 KB |
Output is correct |
81 |
Correct |
2048 ms |
305732 KB |
Output is correct |
82 |
Correct |
920 ms |
279416 KB |
Output is correct |
83 |
Correct |
1410 ms |
270244 KB |
Output is correct |
84 |
Correct |
1462 ms |
301500 KB |
Output is correct |
85 |
Correct |
1485 ms |
301968 KB |
Output is correct |
86 |
Correct |
2 ms |
376 KB |
Output is correct |
87 |
Correct |
2 ms |
508 KB |
Output is correct |
88 |
Correct |
3 ms |
1528 KB |
Output is correct |
89 |
Correct |
3 ms |
1528 KB |
Output is correct |
90 |
Correct |
3 ms |
760 KB |
Output is correct |