#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>
typedef long long llong;
const int MAXN = 2500 + 10;
const int INF = 1e9;
int n, m;
struct BIT
{
int tree[MAXN], max;
inline void reset(const int &_max)
{
max = _max;
std::fill(tree + 1, tree + 1 + max, 0);
}
inline void update(const int &pos, const int &value)
{
for (int idx = pos ; idx <= max ; idx += idx & (-idx))
{
tree[idx] += value;
}
}
inline int query(const int &pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
};
BIT fenwick;
int a[MAXN][MAXN];
int p[MAXN][MAXN];
int up[MAXN][MAXN];
int left[MAXN][MAXN];
int down[MAXN][MAXN];
int right[MAXN][MAXN];
std::stack <int> st[MAXN];
std::queue <int> q[MAXN];
int minRight[MAXN];
int maxLeft[MAXN];
bool isIN[MAXN];
void clearStacks()
{
for (int i = 1 ; i <= std::max(n, m) ; ++i)
{
while (!st[i].empty())
{
st[i].pop();
}
}
}
inline int getSum(int r1, int c1, int r2, int c2)
{
--r1; --c1;
return p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1];
}
inline int getSum2(int r1, int c1, int r2, int c2)
{
--r1; --c1;
return (r2 - r1) * (c2 - c1) - (p[r2][c2] - p[r1][c2] - p[r2][c1] + p[r1][c1]);
}
llong count_rectangles(std::vector <std::vector <int>> A)
{
bool zeroOne = true;
n = A.size(); m = A[0].size();
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= m ; ++j)
{
a[i][j] = A[i - 1][j - 1];
p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
zeroOne &= (a[i][j] < 2);
}
}
for (int i = 0 ; i <= m + 1 ; ++i)
{
a[0][i] = a[n + 1][i] = INF;
}
for (int i = 0 ; i <= n + 1 ; ++i)
{
a[i][0] = a[i][m + 1] = INF;
}
if (n <= 2 || m <= 2)
{
return 0;
}
// up
for (int i = 1 ; i <= m ; ++i)
{
st[i].push(0);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[col].empty() && a[st[col].top()][col] < a[row][col])
{
st[col].pop();
}
up[row][col] = st[col].top();
st[col].push(row);
}
}
// down
clearStacks();
for (int i = 1 ; i <= m ; ++i)
{
st[i].push(n + 1);
}
for (int row = n ; row >= 1 ; --row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[col].empty() && (a[st[col].top()][col] < a[row][col] || (zeroOne && a[st[col].top()][col] == a[row][col])))
{
st[col].pop();
}
down[row][col] = st[col].top();
st[col].push(row);
}
}
// left
clearStacks();
for (int i = 1 ; i <= n ; ++i)
{
st[i].push(0);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = 1 ; col <= m ; ++col)
{
while (!st[row].empty() && a[row][st[row].top()] < a[row][col])
{
st[row].pop();
}
left[row][col] = st[row].top();
st[row].push(col);
}
}
// right
clearStacks();
for (int i = 1 ; i <= n ; ++i)
{
st[i].push(m + 1);
}
for (int row = 1 ; row <= n ; ++row)
{
for (int col = m ; col >= 1 ; --col)
{
while (!st[row].empty() && (a[row][st[row].top()] < a[row][col] || (zeroOne && a[row][st[row].top()] == a[row][col])))
{
st[row].pop();
}
right[row][col] = st[row].top();
st[row].push(col);
}
}
llong ans = 0;
if (zeroOne)
{
for (int r1 = 2 ; r1 <= n ; ++r1)
{
for (int c1 = 2 ; c1 <= m ; ++c1)
{
if (a[r1 - 1][c1] == 0 || a[r1][c1 - 1] == 0 || a[r1][c1] == 1)
{
continue;
}
int c2 = right[r1][c1] - 1;
if (c2 < m)
{
int r2 = down[r1][c2] - 1;
if (r2 < n && getSum(r1, c1, r2, c2) == 0 && getSum2(r1 - 1, c1, r1 - 1, c2) == 0 && getSum2(r1, c1 - 1, r2, c1 - 1) == 0 && getSum2(r2 + 1, c1, r2 + 1, c2) == 0 && getSum2(r1, c2 + 1, r2, c2 + 1) == 0)
{
ans++;
}
}
}
}
return ans;
}
for (int r1 = 1 ; r1 + 2 <= n ; ++r1)
{
for (int r2 = r1 + 2 ; r2 <= n ; ++r2)
{
for (int c1 = 1 ; c1 + 2 <= m ; ++c1)
{
for (int c2 = c1 + 2 ; c2 <= m ; ++c2)
{
bool good = true;
for (int col = c1 + 1 ; col < c2 && good ; ++col)
{
if (down[r1][col] < r2 || up[r2][col] > r1)
{
good = false;
}
}
for (int row = r1 + 1 ; row < r2 && good ; ++row)
{
if (right[row][c1] < c2 || left[row][c2] > c1)
{
good = false;
}
}
ans += good;
}
}
}
}
return ans;
for (int row1 = 1 ; row1 + 2 <= n ; ++row1)
{
for (int col = 1 ; col <= m ; ++col)
{
maxLeft[col] = 0;
minRight[col] = INF;
}
for (int row2 = row1 + 2 ; row2 <= n ; ++row2)
{
for (int col = 1 ; col <= m ; ++col)
{
maxLeft[col] = std::max(maxLeft[col], left[row2 - 1][col]);
minRight[col] = std::min(minRight[col], right[row2 - 1][col]);
while (!q[col].empty()) q[col].pop();
isIN[col] = false;
}
fenwick.reset(m);
int need = m;
int ptr = m;
for (int col = m ; col >= 1 ; --col)
{
if (col != m)
{
need = std::min(need, minRight[col + 1]);
if (down[row1][col + 1] < row2 || up[row2][col + 1] > row1)
{
need = col + 1;
}
}
while (!q[col].empty())
{
int top = q[col].front();
if (isIN[top]) fenwick.update(top, -1);
isIN[top] = false;
q[col].pop();
}
while (ptr > need)
{
if (isIN[ptr])
{
fenwick.update(ptr, -1);
isIN[ptr] = false;
}
ptr--;
}
if (col + 1 != need)
{
ans += fenwick.query(need) - isIN[col + 1];
}
isIN[col] = true;
fenwick.update(col, 1);
if (maxLeft[col]) q[maxLeft[col] - 1].push(col);
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
3 ms |
4436 KB |
Output is correct |
6 |
Correct |
7 ms |
4436 KB |
Output is correct |
7 |
Correct |
5 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
3952 KB |
Output is correct |
9 |
Correct |
4 ms |
4436 KB |
Output is correct |
10 |
Correct |
3 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4472 KB |
Output is correct |
12 |
Correct |
4 ms |
4436 KB |
Output is correct |
13 |
Correct |
3 ms |
3668 KB |
Output is correct |
14 |
Correct |
4 ms |
3796 KB |
Output is correct |
15 |
Correct |
4 ms |
3924 KB |
Output is correct |
16 |
Correct |
3 ms |
3796 KB |
Output is correct |
17 |
Correct |
3 ms |
3668 KB |
Output is correct |
18 |
Correct |
3 ms |
3668 KB |
Output is correct |
19 |
Correct |
3 ms |
4436 KB |
Output is correct |
20 |
Correct |
3 ms |
4436 KB |
Output is correct |
21 |
Correct |
2 ms |
3668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
3 ms |
4436 KB |
Output is correct |
6 |
Correct |
7 ms |
4436 KB |
Output is correct |
7 |
Correct |
5 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
3952 KB |
Output is correct |
9 |
Correct |
4 ms |
4436 KB |
Output is correct |
10 |
Correct |
3 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4472 KB |
Output is correct |
12 |
Correct |
4 ms |
4436 KB |
Output is correct |
13 |
Correct |
3 ms |
3668 KB |
Output is correct |
14 |
Correct |
4 ms |
3796 KB |
Output is correct |
15 |
Correct |
4 ms |
3924 KB |
Output is correct |
16 |
Correct |
3 ms |
3796 KB |
Output is correct |
17 |
Correct |
3 ms |
3668 KB |
Output is correct |
18 |
Correct |
3 ms |
3668 KB |
Output is correct |
19 |
Correct |
3 ms |
4436 KB |
Output is correct |
20 |
Correct |
3 ms |
4436 KB |
Output is correct |
21 |
Correct |
2 ms |
3668 KB |
Output is correct |
22 |
Correct |
36 ms |
5804 KB |
Output is correct |
23 |
Correct |
37 ms |
5876 KB |
Output is correct |
24 |
Correct |
35 ms |
5860 KB |
Output is correct |
25 |
Correct |
29 ms |
5844 KB |
Output is correct |
26 |
Correct |
28 ms |
5716 KB |
Output is correct |
27 |
Correct |
29 ms |
5852 KB |
Output is correct |
28 |
Correct |
27 ms |
5844 KB |
Output is correct |
29 |
Correct |
9 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
3 ms |
4436 KB |
Output is correct |
6 |
Correct |
7 ms |
4436 KB |
Output is correct |
7 |
Correct |
5 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
3952 KB |
Output is correct |
9 |
Correct |
4 ms |
4436 KB |
Output is correct |
10 |
Correct |
3 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4472 KB |
Output is correct |
12 |
Correct |
4 ms |
4436 KB |
Output is correct |
13 |
Correct |
3 ms |
3668 KB |
Output is correct |
14 |
Correct |
4 ms |
3796 KB |
Output is correct |
15 |
Correct |
4 ms |
3924 KB |
Output is correct |
16 |
Correct |
3 ms |
3796 KB |
Output is correct |
17 |
Correct |
36 ms |
5804 KB |
Output is correct |
18 |
Correct |
37 ms |
5876 KB |
Output is correct |
19 |
Correct |
35 ms |
5860 KB |
Output is correct |
20 |
Correct |
29 ms |
5844 KB |
Output is correct |
21 |
Correct |
28 ms |
5716 KB |
Output is correct |
22 |
Correct |
29 ms |
5852 KB |
Output is correct |
23 |
Correct |
27 ms |
5844 KB |
Output is correct |
24 |
Correct |
9 ms |
5716 KB |
Output is correct |
25 |
Correct |
3 ms |
3668 KB |
Output is correct |
26 |
Correct |
3 ms |
3668 KB |
Output is correct |
27 |
Correct |
3 ms |
4436 KB |
Output is correct |
28 |
Correct |
3 ms |
4436 KB |
Output is correct |
29 |
Correct |
2 ms |
3668 KB |
Output is correct |
30 |
Correct |
1228 ms |
10108 KB |
Output is correct |
31 |
Correct |
1166 ms |
10108 KB |
Output is correct |
32 |
Correct |
1160 ms |
10196 KB |
Output is correct |
33 |
Correct |
938 ms |
9860 KB |
Output is correct |
34 |
Correct |
931 ms |
9940 KB |
Output is correct |
35 |
Correct |
922 ms |
10092 KB |
Output is correct |
36 |
Correct |
922 ms |
10068 KB |
Output is correct |
37 |
Correct |
900 ms |
10036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
3 ms |
4436 KB |
Output is correct |
6 |
Correct |
7 ms |
4436 KB |
Output is correct |
7 |
Correct |
5 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
3952 KB |
Output is correct |
9 |
Correct |
4 ms |
4436 KB |
Output is correct |
10 |
Correct |
3 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4472 KB |
Output is correct |
12 |
Correct |
4 ms |
4436 KB |
Output is correct |
13 |
Correct |
3 ms |
3668 KB |
Output is correct |
14 |
Correct |
4 ms |
3796 KB |
Output is correct |
15 |
Correct |
4 ms |
3924 KB |
Output is correct |
16 |
Correct |
3 ms |
3796 KB |
Output is correct |
17 |
Correct |
36 ms |
5804 KB |
Output is correct |
18 |
Correct |
37 ms |
5876 KB |
Output is correct |
19 |
Correct |
35 ms |
5860 KB |
Output is correct |
20 |
Correct |
29 ms |
5844 KB |
Output is correct |
21 |
Correct |
28 ms |
5716 KB |
Output is correct |
22 |
Correct |
29 ms |
5852 KB |
Output is correct |
23 |
Correct |
27 ms |
5844 KB |
Output is correct |
24 |
Correct |
9 ms |
5716 KB |
Output is correct |
25 |
Correct |
1228 ms |
10108 KB |
Output is correct |
26 |
Correct |
1166 ms |
10108 KB |
Output is correct |
27 |
Correct |
1160 ms |
10196 KB |
Output is correct |
28 |
Correct |
938 ms |
9860 KB |
Output is correct |
29 |
Correct |
931 ms |
9940 KB |
Output is correct |
30 |
Correct |
922 ms |
10092 KB |
Output is correct |
31 |
Correct |
922 ms |
10068 KB |
Output is correct |
32 |
Correct |
900 ms |
10036 KB |
Output is correct |
33 |
Correct |
3 ms |
3668 KB |
Output is correct |
34 |
Correct |
3 ms |
3668 KB |
Output is correct |
35 |
Correct |
3 ms |
4436 KB |
Output is correct |
36 |
Correct |
3 ms |
4436 KB |
Output is correct |
37 |
Correct |
2 ms |
3668 KB |
Output is correct |
38 |
Execution timed out |
5036 ms |
39928 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1940 ms |
3980 KB |
Output is correct |
2 |
Correct |
1299 ms |
3952 KB |
Output is correct |
3 |
Correct |
2 ms |
3924 KB |
Output is correct |
4 |
Correct |
2 ms |
3668 KB |
Output is correct |
5 |
Correct |
11 ms |
3988 KB |
Output is correct |
6 |
Correct |
11 ms |
4052 KB |
Output is correct |
7 |
Correct |
11 ms |
4064 KB |
Output is correct |
8 |
Correct |
11 ms |
3964 KB |
Output is correct |
9 |
Correct |
11 ms |
4056 KB |
Output is correct |
10 |
Correct |
3 ms |
3796 KB |
Output is correct |
11 |
Correct |
3 ms |
3796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3668 KB |
Output is correct |
2 |
Correct |
3 ms |
3668 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
2 ms |
3668 KB |
Output is correct |
6 |
Correct |
2 ms |
3924 KB |
Output is correct |
7 |
Correct |
258 ms |
104684 KB |
Output is correct |
8 |
Correct |
564 ms |
211388 KB |
Output is correct |
9 |
Correct |
590 ms |
212292 KB |
Output is correct |
10 |
Correct |
555 ms |
211384 KB |
Output is correct |
11 |
Correct |
180 ms |
113504 KB |
Output is correct |
12 |
Correct |
321 ms |
221152 KB |
Output is correct |
13 |
Correct |
345 ms |
216984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
3 ms |
4436 KB |
Output is correct |
6 |
Correct |
7 ms |
4436 KB |
Output is correct |
7 |
Correct |
5 ms |
4456 KB |
Output is correct |
8 |
Correct |
3 ms |
3952 KB |
Output is correct |
9 |
Correct |
4 ms |
4436 KB |
Output is correct |
10 |
Correct |
3 ms |
4436 KB |
Output is correct |
11 |
Correct |
4 ms |
4472 KB |
Output is correct |
12 |
Correct |
4 ms |
4436 KB |
Output is correct |
13 |
Correct |
3 ms |
3668 KB |
Output is correct |
14 |
Correct |
4 ms |
3796 KB |
Output is correct |
15 |
Correct |
4 ms |
3924 KB |
Output is correct |
16 |
Correct |
3 ms |
3796 KB |
Output is correct |
17 |
Correct |
36 ms |
5804 KB |
Output is correct |
18 |
Correct |
37 ms |
5876 KB |
Output is correct |
19 |
Correct |
35 ms |
5860 KB |
Output is correct |
20 |
Correct |
29 ms |
5844 KB |
Output is correct |
21 |
Correct |
28 ms |
5716 KB |
Output is correct |
22 |
Correct |
29 ms |
5852 KB |
Output is correct |
23 |
Correct |
27 ms |
5844 KB |
Output is correct |
24 |
Correct |
9 ms |
5716 KB |
Output is correct |
25 |
Correct |
1228 ms |
10108 KB |
Output is correct |
26 |
Correct |
1166 ms |
10108 KB |
Output is correct |
27 |
Correct |
1160 ms |
10196 KB |
Output is correct |
28 |
Correct |
938 ms |
9860 KB |
Output is correct |
29 |
Correct |
931 ms |
9940 KB |
Output is correct |
30 |
Correct |
922 ms |
10092 KB |
Output is correct |
31 |
Correct |
922 ms |
10068 KB |
Output is correct |
32 |
Correct |
900 ms |
10036 KB |
Output is correct |
33 |
Execution timed out |
5036 ms |
39928 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |