#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
const int MX = 2505;
int cl[MX][MX]; // smallest row>i on same column containing one
int nxt[MX][MX]; // furthest col on same row tel que same close
int cum[MX][MX]; // normal cum on columns
int gimme(int col,int a,int b){
return cum[b][col] - (a?cum[a-1][col]:0);
}
ll count_rectangles(vector<vector<int> > a) {
ll ans=0;
int n=sz(a),m=sz(a[0]);
bool f=1;
for (int j = 0; j < m; ++j)
{
int last=-1;
for (int i = n-1; i >= 0; i--){
if(a[i][j]>1)f=0;
if(a[i][j]){
cl[i][j]=last,last=i;
if((i+1) == cl[i][j])cl[i][j]=-1;
}
else cl[i][j]=-1;
}
}
if(!f){
for (int r1 = 1; r1 <= n-2; ++r1)
for (int r2 = r1; r2 <= n-2; ++r2)
for (int c1 = 1; c1 <= m-2; ++c1)
for (int c2 = c1; c2 <= m-2; ++c2)
{
bool ok=1;
for (int i = r1; i <= r2; ++i){
for (int j = c1; j <= c2; ++j)
if(a[i][j]>=a[i][c1-1] || a[i][j]>=a[i][c2+1] || a[i][j]>=a[r1-1][j] || a[i][j]>=a[r2+1][j]){ok=0;break;}
if(!ok)break;
}
ans+=ok;
}
return ans;
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; )
{
if(cl[i][j]==-1){
nxt[i][j]=-1,j++;
continue;
}
int z=j;
while(z<m && cl[i][z]==cl[i][j])
z++;
for (int A = j; A < z; ++A)
nxt[i][A]=z;
j=z;
}
for (int j = 0; j < m; ++j){
cum[i][j]=(!a[i][j]);
if(i)cum[i][j]+=cum[i-1][j];
}
}
for (int i = 0; i < n-2; ++i)
for (int j = 1; j < m-1; ++j)
if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && nxt[i][j]!=m && !gimme(nxt[i][j],i+1,cl[i][j]-1))
ans++;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 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 |
640 KB |
Output is correct |
20 |
Correct |
1 ms |
640 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
46 ms |
768 KB |
Output is correct |
18 |
Correct |
49 ms |
768 KB |
Output is correct |
19 |
Correct |
45 ms |
776 KB |
Output is correct |
20 |
Correct |
43 ms |
768 KB |
Output is correct |
21 |
Correct |
53 ms |
768 KB |
Output is correct |
22 |
Correct |
54 ms |
768 KB |
Output is correct |
23 |
Correct |
53 ms |
768 KB |
Output is correct |
24 |
Correct |
13 ms |
640 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 |
640 KB |
Output is correct |
28 |
Correct |
1 ms |
640 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
46 ms |
768 KB |
Output is correct |
18 |
Correct |
49 ms |
768 KB |
Output is correct |
19 |
Correct |
45 ms |
776 KB |
Output is correct |
20 |
Correct |
43 ms |
768 KB |
Output is correct |
21 |
Correct |
53 ms |
768 KB |
Output is correct |
22 |
Correct |
54 ms |
768 KB |
Output is correct |
23 |
Correct |
53 ms |
768 KB |
Output is correct |
24 |
Correct |
13 ms |
640 KB |
Output is correct |
25 |
Correct |
1699 ms |
1656 KB |
Output is correct |
26 |
Correct |
1688 ms |
1656 KB |
Output is correct |
27 |
Correct |
1700 ms |
1656 KB |
Output is correct |
28 |
Correct |
1659 ms |
1652 KB |
Output is correct |
29 |
Correct |
2199 ms |
1656 KB |
Output is correct |
30 |
Correct |
2215 ms |
1620 KB |
Output is correct |
31 |
Correct |
2122 ms |
1656 KB |
Output is correct |
32 |
Correct |
2045 ms |
1660 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 |
640 KB |
Output is correct |
36 |
Correct |
1 ms |
640 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
46 ms |
768 KB |
Output is correct |
18 |
Correct |
49 ms |
768 KB |
Output is correct |
19 |
Correct |
45 ms |
776 KB |
Output is correct |
20 |
Correct |
43 ms |
768 KB |
Output is correct |
21 |
Correct |
53 ms |
768 KB |
Output is correct |
22 |
Correct |
54 ms |
768 KB |
Output is correct |
23 |
Correct |
53 ms |
768 KB |
Output is correct |
24 |
Correct |
13 ms |
640 KB |
Output is correct |
25 |
Correct |
1699 ms |
1656 KB |
Output is correct |
26 |
Correct |
1688 ms |
1656 KB |
Output is correct |
27 |
Correct |
1700 ms |
1656 KB |
Output is correct |
28 |
Correct |
1659 ms |
1652 KB |
Output is correct |
29 |
Correct |
2199 ms |
1656 KB |
Output is correct |
30 |
Correct |
2215 ms |
1620 KB |
Output is correct |
31 |
Correct |
2122 ms |
1656 KB |
Output is correct |
32 |
Correct |
2045 ms |
1660 KB |
Output is correct |
33 |
Execution timed out |
5055 ms |
8960 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
384 KB |
Output is correct |
2 |
Correct |
10 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
19 ms |
384 KB |
Output is correct |
6 |
Correct |
19 ms |
384 KB |
Output is correct |
7 |
Correct |
19 ms |
512 KB |
Output is correct |
8 |
Correct |
18 ms |
384 KB |
Output is correct |
9 |
Correct |
18 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
160 ms |
59128 KB |
Output is correct |
3 |
Correct |
347 ms |
122360 KB |
Output is correct |
4 |
Correct |
353 ms |
123000 KB |
Output is correct |
5 |
Correct |
349 ms |
123000 KB |
Output is correct |
6 |
Correct |
133 ms |
60920 KB |
Output is correct |
7 |
Correct |
255 ms |
119928 KB |
Output is correct |
8 |
Correct |
273 ms |
123000 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
12 |
Correct |
1 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
640 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
46 ms |
768 KB |
Output is correct |
18 |
Correct |
49 ms |
768 KB |
Output is correct |
19 |
Correct |
45 ms |
776 KB |
Output is correct |
20 |
Correct |
43 ms |
768 KB |
Output is correct |
21 |
Correct |
53 ms |
768 KB |
Output is correct |
22 |
Correct |
54 ms |
768 KB |
Output is correct |
23 |
Correct |
53 ms |
768 KB |
Output is correct |
24 |
Correct |
13 ms |
640 KB |
Output is correct |
25 |
Correct |
1699 ms |
1656 KB |
Output is correct |
26 |
Correct |
1688 ms |
1656 KB |
Output is correct |
27 |
Correct |
1700 ms |
1656 KB |
Output is correct |
28 |
Correct |
1659 ms |
1652 KB |
Output is correct |
29 |
Correct |
2199 ms |
1656 KB |
Output is correct |
30 |
Correct |
2215 ms |
1620 KB |
Output is correct |
31 |
Correct |
2122 ms |
1656 KB |
Output is correct |
32 |
Correct |
2045 ms |
1660 KB |
Output is correct |
33 |
Execution timed out |
5055 ms |
8960 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |