#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2501;
int m,n;
int s[N][N],r[N][N],u[N][N],d[N][N],l[N][N],mly[N];
long long ans;
void run(int x,int y)
{
r[x][y] = y;
for(int i = 1;;i++)
{
if(y+i>n) break;
if(s[x][y+i]>=s[x][y]) break;
r[x][y] = y+i;
}
l[x][y] = y;
for(int i = 1;;i++)
{
if(y-i<1) break;
if(s[x][y-i]>=s[x][y]) break;
l[x][y] = y-i;
}
d[x][y] = x;
for(int i = 1;;i++)
{
if(x+i>m) break;
if(s[x+i][y]>=s[x][y]) break;
d[x][y] = x+i;
}
u[x][y] = x;
for(int i = 1;;i++)
{
if(x-i<1) break;
if(s[x-i][y]>=s[x][y]) break;
u[x][y] = x-i;
}
}
long long count_rectangles(vector<vector<int> > _a)
{
m = _a.size(),n = _a[0].size();
for(int i = 0;i < m;i++) for(int j = 0;j < n;j++) s[i+1][j+1] = _a[i][j];
for(int i = 1;i <= m;i++) for(int j = 1;j <= n;j++) run(i,j);
for(int i = 1;i <= m;i++) for(int j = i+2;j <= m;j++)
{
for(int x = 2;x <= n;x++)
{
int mn = INT_MAX;
for(int k = i+1;k < j;k++) mn = min(mn,r[k][x-1]);
for(int y = x;y <= min(mn,n-1);y++)
{
// cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << d[i][y] << ' ' << u[j][y] << endl;
if(d[i][y]<j-1 or u[j][y]>i+1) break;
int mx = INT_MIN;
for(int k = i+1;k < j;k++) mx = max(mx,l[k][y+1]);
// cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << mx << endl;
// if(mx<=x) cout << i << ' ' << j << ' ' << x << ' ' << y << endl,ans++;
if(mx<=x) ans++;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
1024 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
496 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
896 KB |
Output is correct |
20 |
Correct |
1 ms |
896 KB |
Output is correct |
21 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
1024 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
496 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
21 ms |
2176 KB |
Output is correct |
18 |
Correct |
21 ms |
2176 KB |
Output is correct |
19 |
Correct |
21 ms |
2176 KB |
Output is correct |
20 |
Correct |
9 ms |
2176 KB |
Output is correct |
21 |
Correct |
9 ms |
2304 KB |
Output is correct |
22 |
Correct |
9 ms |
2176 KB |
Output is correct |
23 |
Correct |
12 ms |
2176 KB |
Output is correct |
24 |
Correct |
6 ms |
2048 KB |
Output is correct |
25 |
Correct |
0 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
896 KB |
Output is correct |
28 |
Correct |
1 ms |
896 KB |
Output is correct |
29 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
1024 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
496 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
21 ms |
2176 KB |
Output is correct |
18 |
Correct |
21 ms |
2176 KB |
Output is correct |
19 |
Correct |
21 ms |
2176 KB |
Output is correct |
20 |
Correct |
9 ms |
2176 KB |
Output is correct |
21 |
Correct |
9 ms |
2304 KB |
Output is correct |
22 |
Correct |
9 ms |
2176 KB |
Output is correct |
23 |
Correct |
12 ms |
2176 KB |
Output is correct |
24 |
Correct |
6 ms |
2048 KB |
Output is correct |
25 |
Correct |
795 ms |
5776 KB |
Output is correct |
26 |
Correct |
794 ms |
5752 KB |
Output is correct |
27 |
Correct |
797 ms |
5880 KB |
Output is correct |
28 |
Correct |
305 ms |
5624 KB |
Output is correct |
29 |
Correct |
304 ms |
5752 KB |
Output is correct |
30 |
Correct |
314 ms |
5880 KB |
Output is correct |
31 |
Correct |
311 ms |
5760 KB |
Output is correct |
32 |
Correct |
304 ms |
5856 KB |
Output is correct |
33 |
Correct |
0 ms |
384 KB |
Output is correct |
34 |
Correct |
0 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
896 KB |
Output is correct |
36 |
Correct |
1 ms |
896 KB |
Output is correct |
37 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
1024 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
496 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
21 ms |
2176 KB |
Output is correct |
18 |
Correct |
21 ms |
2176 KB |
Output is correct |
19 |
Correct |
21 ms |
2176 KB |
Output is correct |
20 |
Correct |
9 ms |
2176 KB |
Output is correct |
21 |
Correct |
9 ms |
2304 KB |
Output is correct |
22 |
Correct |
9 ms |
2176 KB |
Output is correct |
23 |
Correct |
12 ms |
2176 KB |
Output is correct |
24 |
Correct |
6 ms |
2048 KB |
Output is correct |
25 |
Correct |
795 ms |
5776 KB |
Output is correct |
26 |
Correct |
794 ms |
5752 KB |
Output is correct |
27 |
Correct |
797 ms |
5880 KB |
Output is correct |
28 |
Correct |
305 ms |
5624 KB |
Output is correct |
29 |
Correct |
304 ms |
5752 KB |
Output is correct |
30 |
Correct |
314 ms |
5880 KB |
Output is correct |
31 |
Correct |
311 ms |
5760 KB |
Output is correct |
32 |
Correct |
304 ms |
5856 KB |
Output is correct |
33 |
Execution timed out |
5073 ms |
30968 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
640 KB |
Output is correct |
2 |
Correct |
11 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
496 KB |
Output is correct |
2 |
Execution timed out |
5082 ms |
88696 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
1024 KB |
Output is correct |
4 |
Correct |
1 ms |
896 KB |
Output is correct |
5 |
Correct |
1 ms |
896 KB |
Output is correct |
6 |
Correct |
1 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
896 KB |
Output is correct |
10 |
Correct |
1 ms |
896 KB |
Output is correct |
11 |
Correct |
1 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
496 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
21 ms |
2176 KB |
Output is correct |
18 |
Correct |
21 ms |
2176 KB |
Output is correct |
19 |
Correct |
21 ms |
2176 KB |
Output is correct |
20 |
Correct |
9 ms |
2176 KB |
Output is correct |
21 |
Correct |
9 ms |
2304 KB |
Output is correct |
22 |
Correct |
9 ms |
2176 KB |
Output is correct |
23 |
Correct |
12 ms |
2176 KB |
Output is correct |
24 |
Correct |
6 ms |
2048 KB |
Output is correct |
25 |
Correct |
795 ms |
5776 KB |
Output is correct |
26 |
Correct |
794 ms |
5752 KB |
Output is correct |
27 |
Correct |
797 ms |
5880 KB |
Output is correct |
28 |
Correct |
305 ms |
5624 KB |
Output is correct |
29 |
Correct |
304 ms |
5752 KB |
Output is correct |
30 |
Correct |
314 ms |
5880 KB |
Output is correct |
31 |
Correct |
311 ms |
5760 KB |
Output is correct |
32 |
Correct |
304 ms |
5856 KB |
Output is correct |
33 |
Execution timed out |
5073 ms |
30968 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |