#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define ff first
#define ss second
const int nax = 2505;
const int nax2 = 205;
int nx[4] = {0, 0, -1, 1};
int ny[4] = {1, -1, 0, 0};
int n, m;
vector<vi> A;
ll ans = 0ll;
int LG[nax];
int spr[nax][nax][12];
int spc[nax][nax][12];
int prefr[nax2][nax2][nax2];
int prefc[nax2][nax2][nax2];
int maxir(int row, int l, int r)
{
int j = LG[r - l + 1];
return max(spr[row][l][j], spr[row][r - (1 << j) + 1][j]);
}
int maxic(int col, int l, int r)
{
int j = LG[r - l + 1];
return max(spc[col][l][j], spc[col][r - (1 << j) + 1][j]);
}
void init()
{
LG[1] = 0;
for(int i = 2; i < nax; i++)
LG[i] = LG[i/2] + 1;
for(int row = 0; row < n; row++)
{
for(int col = 0; col < m; col++)
spr[row][col][0] = spc[col][row][0] = A[row][col];
}
for(int j = 1; j < 12; j++)
{
for(int row = 0; row < n; row++)
{
for(int col = 0; col < m; col++)
{
spr[row][col][j] = max(spr[row][col][j - 1], spr[row][col + (1 << (j - 1))][j - 1]);
spc[col][row][j] = max(spc[col][row][j - 1], spc[col][row + (1 << (j - 1))][j - 1]);
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = i + 2; j < n; j++)
{
for(int k = 0; k < m; k++)
{
prefr[i][j][k + 1] = prefr[i][j][k] + (min(A[i][k], A[j][k]) <= maxic(k, i + 1, j -1)) ;
}
}
}
for(int i = 0 ;i < m; i ++)
{
for(int j = i + 2; j < m; j++)
{
for(int k = 0; k < n; k++)
{
prefc[i][j][k + 1] = prefc[i][j][k] + (min(A[k][i], A[k][j]) <= maxir(k, i + 1, j - 1));
}
}
}
}
ll count_rectangles(vector<vi> a)
{
n = a.size();
m = a[0].size();
A= a;
if(n <= 2 || m <= 2)
return 0ll;
init();
for(int i = 1; i < n - 1;i ++)
{
for(int j = i; j < n - 1; j++)
{
for(int k = 1; k < m - 1; k++)
{
for(int l = k; l < m - 1; l++)
{
if(prefr[i - 1][j + 1][l + 1] - prefr[i - 1][j + 1][k] == 0
&& prefc[k - 1][l + 1][j + 1] - prefc[k - 1][l + 1][i] == 0)
{
ans++;
//;cout << i << ' ' << k << ' ' << j << ' '<< l << '\n';
}
}
}
}
}
return ans;
}
/*
int32_t main()
{
freopen("01.in", "r", stdin);
int N, M;
cin >> N >> M;
vector<vi> a(N);
for(int i = 0; i < N; i++)
{
a[i].resize(M);
for(int j = 0; j < M; j++)
cin >> a[i][j];
}
cout << count_rectangles(a);
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1492 KB |
Output is correct |
3 |
Correct |
1 ms |
1492 KB |
Output is correct |
4 |
Correct |
2 ms |
1492 KB |
Output is correct |
5 |
Correct |
1 ms |
1492 KB |
Output is correct |
6 |
Correct |
2 ms |
1492 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
2 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
2 ms |
1460 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
2 ms |
1492 KB |
Output is correct |
20 |
Correct |
1 ms |
1108 KB |
Output is correct |
21 |
Correct |
0 ms |
304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1492 KB |
Output is correct |
3 |
Correct |
1 ms |
1492 KB |
Output is correct |
4 |
Correct |
2 ms |
1492 KB |
Output is correct |
5 |
Correct |
1 ms |
1492 KB |
Output is correct |
6 |
Correct |
2 ms |
1492 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
2 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
2 ms |
1460 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
2 ms |
1492 KB |
Output is correct |
20 |
Correct |
1 ms |
1108 KB |
Output is correct |
21 |
Correct |
0 ms |
304 KB |
Output is correct |
22 |
Correct |
13 ms |
7244 KB |
Output is correct |
23 |
Correct |
14 ms |
7252 KB |
Output is correct |
24 |
Correct |
12 ms |
7228 KB |
Output is correct |
25 |
Correct |
12 ms |
7224 KB |
Output is correct |
26 |
Correct |
12 ms |
7124 KB |
Output is correct |
27 |
Correct |
12 ms |
7124 KB |
Output is correct |
28 |
Correct |
15 ms |
7240 KB |
Output is correct |
29 |
Correct |
8 ms |
4696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1492 KB |
Output is correct |
3 |
Correct |
1 ms |
1492 KB |
Output is correct |
4 |
Correct |
2 ms |
1492 KB |
Output is correct |
5 |
Correct |
1 ms |
1492 KB |
Output is correct |
6 |
Correct |
2 ms |
1492 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
2 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
2 ms |
1460 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
7244 KB |
Output is correct |
18 |
Correct |
14 ms |
7252 KB |
Output is correct |
19 |
Correct |
12 ms |
7228 KB |
Output is correct |
20 |
Correct |
12 ms |
7224 KB |
Output is correct |
21 |
Correct |
12 ms |
7124 KB |
Output is correct |
22 |
Correct |
12 ms |
7124 KB |
Output is correct |
23 |
Correct |
15 ms |
7240 KB |
Output is correct |
24 |
Correct |
8 ms |
4696 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
2 ms |
1492 KB |
Output is correct |
28 |
Correct |
1 ms |
1108 KB |
Output is correct |
29 |
Correct |
0 ms |
304 KB |
Output is correct |
30 |
Correct |
315 ms |
39716 KB |
Output is correct |
31 |
Correct |
259 ms |
39720 KB |
Output is correct |
32 |
Correct |
247 ms |
39800 KB |
Output is correct |
33 |
Correct |
246 ms |
39572 KB |
Output is correct |
34 |
Correct |
277 ms |
39648 KB |
Output is correct |
35 |
Correct |
248 ms |
39936 KB |
Output is correct |
36 |
Correct |
266 ms |
39764 KB |
Output is correct |
37 |
Correct |
269 ms |
39248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1492 KB |
Output is correct |
3 |
Correct |
1 ms |
1492 KB |
Output is correct |
4 |
Correct |
2 ms |
1492 KB |
Output is correct |
5 |
Correct |
1 ms |
1492 KB |
Output is correct |
6 |
Correct |
2 ms |
1492 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
2 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
2 ms |
1460 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
7244 KB |
Output is correct |
18 |
Correct |
14 ms |
7252 KB |
Output is correct |
19 |
Correct |
12 ms |
7228 KB |
Output is correct |
20 |
Correct |
12 ms |
7224 KB |
Output is correct |
21 |
Correct |
12 ms |
7124 KB |
Output is correct |
22 |
Correct |
12 ms |
7124 KB |
Output is correct |
23 |
Correct |
15 ms |
7240 KB |
Output is correct |
24 |
Correct |
8 ms |
4696 KB |
Output is correct |
25 |
Correct |
315 ms |
39716 KB |
Output is correct |
26 |
Correct |
259 ms |
39720 KB |
Output is correct |
27 |
Correct |
247 ms |
39800 KB |
Output is correct |
28 |
Correct |
246 ms |
39572 KB |
Output is correct |
29 |
Correct |
277 ms |
39648 KB |
Output is correct |
30 |
Correct |
248 ms |
39936 KB |
Output is correct |
31 |
Correct |
266 ms |
39764 KB |
Output is correct |
32 |
Correct |
269 ms |
39248 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
2 ms |
1492 KB |
Output is correct |
36 |
Correct |
1 ms |
1108 KB |
Output is correct |
37 |
Correct |
0 ms |
304 KB |
Output is correct |
38 |
Execution timed out |
5021 ms |
173584 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
232 ms |
397148 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
1492 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
0 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Execution timed out |
5063 ms |
331700 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1492 KB |
Output is correct |
3 |
Correct |
1 ms |
1492 KB |
Output is correct |
4 |
Correct |
2 ms |
1492 KB |
Output is correct |
5 |
Correct |
1 ms |
1492 KB |
Output is correct |
6 |
Correct |
2 ms |
1492 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
2 ms |
1492 KB |
Output is correct |
10 |
Correct |
2 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1492 KB |
Output is correct |
12 |
Correct |
2 ms |
1460 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
13 ms |
7244 KB |
Output is correct |
18 |
Correct |
14 ms |
7252 KB |
Output is correct |
19 |
Correct |
12 ms |
7228 KB |
Output is correct |
20 |
Correct |
12 ms |
7224 KB |
Output is correct |
21 |
Correct |
12 ms |
7124 KB |
Output is correct |
22 |
Correct |
12 ms |
7124 KB |
Output is correct |
23 |
Correct |
15 ms |
7240 KB |
Output is correct |
24 |
Correct |
8 ms |
4696 KB |
Output is correct |
25 |
Correct |
315 ms |
39716 KB |
Output is correct |
26 |
Correct |
259 ms |
39720 KB |
Output is correct |
27 |
Correct |
247 ms |
39800 KB |
Output is correct |
28 |
Correct |
246 ms |
39572 KB |
Output is correct |
29 |
Correct |
277 ms |
39648 KB |
Output is correct |
30 |
Correct |
248 ms |
39936 KB |
Output is correct |
31 |
Correct |
266 ms |
39764 KB |
Output is correct |
32 |
Correct |
269 ms |
39248 KB |
Output is correct |
33 |
Execution timed out |
5021 ms |
173584 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |