#include "rect.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
const ll INF=1000000001;
//struct node{
// ll l;
// ll r;
// ll left;
// ll right;
// ll minimo;
//}
//ll counter;
//void create_tree(ll ind1, ll ind2, ll l, ll r){
// st[ind1][ind2][counter].l=l;
// st[ind1][ind2][counter].l=r;
// if (l!=r){
// ll menor;
// ll ind3=counter;
// counter++;
// st[ind1][ind2][ind3].left=counter;
// menor=min(menor,create_tree(ind1,ind2,l,(l+r)/2));
// counter++;
// st[ind1][ind2][ind3].right=counter;
// menor=min(menor,create_tree(ind1,ind2,(l+r)/2+1,r);
// }
// else{
// if (ind1==1) return
// }
//}
//vector<vector<vector<node>>> st;
bool esbinario (vvi v){
for (vi x:v){
for (int y:x){
if (y>1) return false;
}
}
return true;
}
ll casobinario(vvi v){
//cerr<<"a";
ll n=v.size();
ll m=v[0].size();
vvii g(n,vii(m,pii{0,0}));
for (ll i=1;i<n-1;i++){
for (ll j=1;j<m-1;j++){
if (v[i][j]==1) continue;
if (v[i-1][j]==1){
ll x=i;
while (x<n and v[x][j]==0) x++;
x--;
if (x!=n) g[i][j].first=x;
}
if (v[i][j-1]==1){
ll x=j;
while (x<m and v[i][x]==0) x++;
x--;
if (x!=m) g[i][j].second=x;
}
}
}
//cerr << g[1][2].first << ' ' << g[1][2].second << '\n';
ll sol=0;
for (ll i=1;i<n-1;i++){
for (ll j=1;j<m-1;j++){
if (g[i][j].first and g[i][j].second){
bool T=true;
for (ll a=i;a<=g[i][j].first;a++){
if (g[a][j].second!=g[i][j].second){
T=false;
break;
}
}
if (T){
for (ll a=j;a<=g[i][j].second;a++){
if (g[i][a].first!=g[i][j].first){
T=false;
break;
}
}
}
if (T){
//cerr << i << ' ' << j << '\n';
sol++;
}
}
}
}
return sol;
}
long long count_rectangles(std::vector<std::vector<int> > v) {
if(esbinario(v)) return casobinario(v);
ll sol=0;
ll n=v.size();
ll m=v[0].size();
//st=vector<vector<vector<node>>>(2,vector<vector<node>>(1000),vector<node>(2000));
//vvvi;
for (ll i1=1;i1<n-1;i1++){
for (ll j1=1;j1<m-1;j1++){
if (v[i1][j1]>=min(v[i1-1][j1],v[i1][j1-1])) continue;
for (ll i2=i1;i2<n-1;i2++){
for (ll j2=j1;j2<m-1;j2++){
bool T=true;
for (ll x=i1;x<=i2;x++){
for (ll y=j1;y<=j2;y++){
if (v[x][y]>=min(min(v[i1-1][y],v[i2+1][y]),min(v[x][j1-1],v[x][j2+1]))){
T=false;
break;
}
}
if (T==false) break;
}
//ll menor=INF;
//for (ll x=i1;x<=i2;x++) menor=min(menor,min(v[x][j1-1],v[x][j2+1]));
//for (ll x=j1;x<=j2;x++) menor=min(menor,min(v[i1-1][x],v[i2+1][x]));
//if (vi{i1,i2,j1,j2}==vi{1,2,1,1}) cerr << mayor << ' '<<menor<<'\n';
//if (mayor<menor){
// sol++;
//cerr << i1<<' '<<i2<<' '<<j1<<' '<<j2<<' '<<mayor<<' '<<menor<<'\n';
//}
if (T){
sol++;
//cerr<<i1<<' '<<i2<<' '<<j1<<' '<<j2<<'\n';
}
}
}
}
}
return sol;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
51 ms |
332 KB |
Output is correct |
23 |
Correct |
51 ms |
332 KB |
Output is correct |
24 |
Correct |
51 ms |
332 KB |
Output is correct |
25 |
Correct |
12 ms |
368 KB |
Output is correct |
26 |
Correct |
19 ms |
372 KB |
Output is correct |
27 |
Correct |
22 ms |
364 KB |
Output is correct |
28 |
Correct |
21 ms |
368 KB |
Output is correct |
29 |
Correct |
5 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
51 ms |
332 KB |
Output is correct |
18 |
Correct |
51 ms |
332 KB |
Output is correct |
19 |
Correct |
51 ms |
332 KB |
Output is correct |
20 |
Correct |
12 ms |
368 KB |
Output is correct |
21 |
Correct |
19 ms |
372 KB |
Output is correct |
22 |
Correct |
22 ms |
364 KB |
Output is correct |
23 |
Correct |
21 ms |
368 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1987 ms |
716 KB |
Output is correct |
31 |
Correct |
2032 ms |
760 KB |
Output is correct |
32 |
Correct |
1991 ms |
756 KB |
Output is correct |
33 |
Correct |
374 ms |
836 KB |
Output is correct |
34 |
Correct |
752 ms |
716 KB |
Output is correct |
35 |
Correct |
771 ms |
836 KB |
Output is correct |
36 |
Correct |
689 ms |
776 KB |
Output is correct |
37 |
Correct |
682 ms |
740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
51 ms |
332 KB |
Output is correct |
18 |
Correct |
51 ms |
332 KB |
Output is correct |
19 |
Correct |
51 ms |
332 KB |
Output is correct |
20 |
Correct |
12 ms |
368 KB |
Output is correct |
21 |
Correct |
19 ms |
372 KB |
Output is correct |
22 |
Correct |
22 ms |
364 KB |
Output is correct |
23 |
Correct |
21 ms |
368 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
25 |
Correct |
1987 ms |
716 KB |
Output is correct |
26 |
Correct |
2032 ms |
760 KB |
Output is correct |
27 |
Correct |
1991 ms |
756 KB |
Output is correct |
28 |
Correct |
374 ms |
836 KB |
Output is correct |
29 |
Correct |
752 ms |
716 KB |
Output is correct |
30 |
Correct |
771 ms |
836 KB |
Output is correct |
31 |
Correct |
689 ms |
776 KB |
Output is correct |
32 |
Correct |
682 ms |
740 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
602 ms |
6068 KB |
Output is correct |
39 |
Execution timed out |
5097 ms |
6092 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
332 KB |
Output is correct |
2 |
Correct |
12 ms |
372 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
8 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
332 KB |
Output is correct |
7 |
Correct |
8 ms |
332 KB |
Output is correct |
8 |
Correct |
8 ms |
332 KB |
Output is correct |
9 |
Correct |
7 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
133 ms |
79076 KB |
Output is correct |
8 |
Correct |
288 ms |
183276 KB |
Output is correct |
9 |
Correct |
286 ms |
184012 KB |
Output is correct |
10 |
Correct |
289 ms |
184196 KB |
Output is correct |
11 |
Correct |
90 ms |
91008 KB |
Output is correct |
12 |
Correct |
201 ms |
172848 KB |
Output is correct |
13 |
Correct |
215 ms |
184140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
51 ms |
332 KB |
Output is correct |
18 |
Correct |
51 ms |
332 KB |
Output is correct |
19 |
Correct |
51 ms |
332 KB |
Output is correct |
20 |
Correct |
12 ms |
368 KB |
Output is correct |
21 |
Correct |
19 ms |
372 KB |
Output is correct |
22 |
Correct |
22 ms |
364 KB |
Output is correct |
23 |
Correct |
21 ms |
368 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
25 |
Correct |
1987 ms |
716 KB |
Output is correct |
26 |
Correct |
2032 ms |
760 KB |
Output is correct |
27 |
Correct |
1991 ms |
756 KB |
Output is correct |
28 |
Correct |
374 ms |
836 KB |
Output is correct |
29 |
Correct |
752 ms |
716 KB |
Output is correct |
30 |
Correct |
771 ms |
836 KB |
Output is correct |
31 |
Correct |
689 ms |
776 KB |
Output is correct |
32 |
Correct |
682 ms |
740 KB |
Output is correct |
33 |
Correct |
602 ms |
6068 KB |
Output is correct |
34 |
Execution timed out |
5097 ms |
6092 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |