#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
#define C continue
#define lb lower_bound
typedef long long ll ;
typedef vector < int > vi ;
#include "rect.h"
int n , m ;
int a [209][209] ;
vi ok [209][209][209] ;
int mx [209][209][209][2] ;
long long count_rectangles ( vector <vi> A ) {
n = A .size () ;
m = A [0] .size () ;
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) {
a [i][j] = A [i][j] ;
}
}
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < m ; j ++ ) {
int Mx = 0 ;
for ( int k = j ; k < m ; k ++ ) {
Mx = max ( Mx , a [i][k] ) ;
mx [i][j][k][0] = Mx ;
}
}
}
for ( int k = 0 ; k < m ; k ++ ) {
for ( int i = 0 ; i < n ; i ++ ) {
int Mx = 0 ;
for ( int j = i ; j < n ; j ++ ) {
Mx = max ( Mx , a [j][k] ) ;
mx [k][i][j][1] = Mx ;
}
}
}
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 ( min ( a [i-1][l] , a [j+1][l] ) <= mx [l][i][j][1] ) {
// k = l ;
break ;
}
ok [i][j][k] .pb ( l ) ;
}
}
}
}
ll ans = 0 ;
for ( int k = 1 ; k < m -1 ; k ++ ) {
for ( int l = k ; l < m -1 ; l ++ ) {
for ( int i = 1 ; i < n -1 ; i ++ ) {
for ( int j = i ; j < n -1 ; j ++ ) {
if ( min ( a [j][k-1] , a [j][l+1] ) <= mx [j][k][l][0] ) {
// i = j ;
break ;
}
auto it = lb ( ok [i][j][k] .begin () , ok [i][j][k] .end () , l ) - ok [i][j][k] .begin () ;
if ( it == ok [i][j][k] .size () ) C ;
ans += ( ok [i][j][k][it] == l ) ;
}
}
}
}
return ans ;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:62:49: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if ( it == ok [i][j][k] .size () ) C ;
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214780 KB |
Output is correct |
2 |
Correct |
148 ms |
216312 KB |
Output is correct |
3 |
Correct |
148 ms |
216440 KB |
Output is correct |
4 |
Correct |
148 ms |
216312 KB |
Output is correct |
5 |
Correct |
149 ms |
216312 KB |
Output is correct |
6 |
Correct |
151 ms |
216312 KB |
Output is correct |
7 |
Correct |
148 ms |
215804 KB |
Output is correct |
8 |
Correct |
147 ms |
215800 KB |
Output is correct |
9 |
Correct |
148 ms |
216312 KB |
Output is correct |
10 |
Correct |
150 ms |
216312 KB |
Output is correct |
11 |
Correct |
149 ms |
216440 KB |
Output is correct |
12 |
Correct |
150 ms |
216440 KB |
Output is correct |
13 |
Correct |
146 ms |
214648 KB |
Output is correct |
14 |
Correct |
145 ms |
214780 KB |
Output is correct |
15 |
Correct |
147 ms |
215160 KB |
Output is correct |
16 |
Correct |
146 ms |
214776 KB |
Output is correct |
17 |
Correct |
147 ms |
214776 KB |
Output is correct |
18 |
Correct |
146 ms |
214708 KB |
Output is correct |
19 |
Correct |
145 ms |
216360 KB |
Output is correct |
20 |
Correct |
149 ms |
215928 KB |
Output is correct |
21 |
Correct |
143 ms |
214776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214780 KB |
Output is correct |
2 |
Correct |
148 ms |
216312 KB |
Output is correct |
3 |
Correct |
148 ms |
216440 KB |
Output is correct |
4 |
Correct |
148 ms |
216312 KB |
Output is correct |
5 |
Correct |
149 ms |
216312 KB |
Output is correct |
6 |
Correct |
151 ms |
216312 KB |
Output is correct |
7 |
Correct |
148 ms |
215804 KB |
Output is correct |
8 |
Correct |
147 ms |
215800 KB |
Output is correct |
9 |
Correct |
148 ms |
216312 KB |
Output is correct |
10 |
Correct |
150 ms |
216312 KB |
Output is correct |
11 |
Correct |
149 ms |
216440 KB |
Output is correct |
12 |
Correct |
150 ms |
216440 KB |
Output is correct |
13 |
Correct |
146 ms |
214648 KB |
Output is correct |
14 |
Correct |
145 ms |
214780 KB |
Output is correct |
15 |
Correct |
147 ms |
215160 KB |
Output is correct |
16 |
Correct |
146 ms |
214776 KB |
Output is correct |
17 |
Correct |
167 ms |
227064 KB |
Output is correct |
18 |
Correct |
166 ms |
227196 KB |
Output is correct |
19 |
Correct |
169 ms |
227064 KB |
Output is correct |
20 |
Correct |
164 ms |
225656 KB |
Output is correct |
21 |
Correct |
157 ms |
225784 KB |
Output is correct |
22 |
Correct |
159 ms |
225656 KB |
Output is correct |
23 |
Correct |
169 ms |
225784 KB |
Output is correct |
24 |
Correct |
158 ms |
222968 KB |
Output is correct |
25 |
Correct |
147 ms |
214776 KB |
Output is correct |
26 |
Correct |
146 ms |
214708 KB |
Output is correct |
27 |
Correct |
145 ms |
216360 KB |
Output is correct |
28 |
Correct |
149 ms |
215928 KB |
Output is correct |
29 |
Correct |
143 ms |
214776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214780 KB |
Output is correct |
2 |
Correct |
148 ms |
216312 KB |
Output is correct |
3 |
Correct |
148 ms |
216440 KB |
Output is correct |
4 |
Correct |
148 ms |
216312 KB |
Output is correct |
5 |
Correct |
149 ms |
216312 KB |
Output is correct |
6 |
Correct |
151 ms |
216312 KB |
Output is correct |
7 |
Correct |
148 ms |
215804 KB |
Output is correct |
8 |
Correct |
147 ms |
215800 KB |
Output is correct |
9 |
Correct |
148 ms |
216312 KB |
Output is correct |
10 |
Correct |
150 ms |
216312 KB |
Output is correct |
11 |
Correct |
149 ms |
216440 KB |
Output is correct |
12 |
Correct |
150 ms |
216440 KB |
Output is correct |
13 |
Correct |
146 ms |
214648 KB |
Output is correct |
14 |
Correct |
145 ms |
214780 KB |
Output is correct |
15 |
Correct |
147 ms |
215160 KB |
Output is correct |
16 |
Correct |
146 ms |
214776 KB |
Output is correct |
17 |
Correct |
167 ms |
227064 KB |
Output is correct |
18 |
Correct |
166 ms |
227196 KB |
Output is correct |
19 |
Correct |
169 ms |
227064 KB |
Output is correct |
20 |
Correct |
164 ms |
225656 KB |
Output is correct |
21 |
Correct |
157 ms |
225784 KB |
Output is correct |
22 |
Correct |
159 ms |
225656 KB |
Output is correct |
23 |
Correct |
169 ms |
225784 KB |
Output is correct |
24 |
Correct |
158 ms |
222968 KB |
Output is correct |
25 |
Correct |
446 ms |
304376 KB |
Output is correct |
26 |
Correct |
469 ms |
304504 KB |
Output is correct |
27 |
Correct |
455 ms |
304376 KB |
Output is correct |
28 |
Correct |
297 ms |
281968 KB |
Output is correct |
29 |
Correct |
301 ms |
282648 KB |
Output is correct |
30 |
Correct |
334 ms |
282616 KB |
Output is correct |
31 |
Correct |
299 ms |
283000 KB |
Output is correct |
32 |
Correct |
301 ms |
281976 KB |
Output is correct |
33 |
Correct |
147 ms |
214776 KB |
Output is correct |
34 |
Correct |
146 ms |
214708 KB |
Output is correct |
35 |
Correct |
145 ms |
216360 KB |
Output is correct |
36 |
Correct |
149 ms |
215928 KB |
Output is correct |
37 |
Correct |
143 ms |
214776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214780 KB |
Output is correct |
2 |
Correct |
148 ms |
216312 KB |
Output is correct |
3 |
Correct |
148 ms |
216440 KB |
Output is correct |
4 |
Correct |
148 ms |
216312 KB |
Output is correct |
5 |
Correct |
149 ms |
216312 KB |
Output is correct |
6 |
Correct |
151 ms |
216312 KB |
Output is correct |
7 |
Correct |
148 ms |
215804 KB |
Output is correct |
8 |
Correct |
147 ms |
215800 KB |
Output is correct |
9 |
Correct |
148 ms |
216312 KB |
Output is correct |
10 |
Correct |
150 ms |
216312 KB |
Output is correct |
11 |
Correct |
149 ms |
216440 KB |
Output is correct |
12 |
Correct |
150 ms |
216440 KB |
Output is correct |
13 |
Correct |
146 ms |
214648 KB |
Output is correct |
14 |
Correct |
145 ms |
214780 KB |
Output is correct |
15 |
Correct |
147 ms |
215160 KB |
Output is correct |
16 |
Correct |
146 ms |
214776 KB |
Output is correct |
17 |
Correct |
167 ms |
227064 KB |
Output is correct |
18 |
Correct |
166 ms |
227196 KB |
Output is correct |
19 |
Correct |
169 ms |
227064 KB |
Output is correct |
20 |
Correct |
164 ms |
225656 KB |
Output is correct |
21 |
Correct |
157 ms |
225784 KB |
Output is correct |
22 |
Correct |
159 ms |
225656 KB |
Output is correct |
23 |
Correct |
169 ms |
225784 KB |
Output is correct |
24 |
Correct |
158 ms |
222968 KB |
Output is correct |
25 |
Correct |
446 ms |
304376 KB |
Output is correct |
26 |
Correct |
469 ms |
304504 KB |
Output is correct |
27 |
Correct |
455 ms |
304376 KB |
Output is correct |
28 |
Correct |
297 ms |
281968 KB |
Output is correct |
29 |
Correct |
301 ms |
282648 KB |
Output is correct |
30 |
Correct |
334 ms |
282616 KB |
Output is correct |
31 |
Correct |
299 ms |
283000 KB |
Output is correct |
32 |
Correct |
301 ms |
281976 KB |
Output is correct |
33 |
Runtime error |
438 ms |
443256 KB |
Execution killed with signal 11 |
34 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
457 ms |
447748 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214936 KB |
Output is correct |
2 |
Runtime error |
488 ms |
480684 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
150 ms |
214780 KB |
Output is correct |
2 |
Correct |
148 ms |
216312 KB |
Output is correct |
3 |
Correct |
148 ms |
216440 KB |
Output is correct |
4 |
Correct |
148 ms |
216312 KB |
Output is correct |
5 |
Correct |
149 ms |
216312 KB |
Output is correct |
6 |
Correct |
151 ms |
216312 KB |
Output is correct |
7 |
Correct |
148 ms |
215804 KB |
Output is correct |
8 |
Correct |
147 ms |
215800 KB |
Output is correct |
9 |
Correct |
148 ms |
216312 KB |
Output is correct |
10 |
Correct |
150 ms |
216312 KB |
Output is correct |
11 |
Correct |
149 ms |
216440 KB |
Output is correct |
12 |
Correct |
150 ms |
216440 KB |
Output is correct |
13 |
Correct |
146 ms |
214648 KB |
Output is correct |
14 |
Correct |
145 ms |
214780 KB |
Output is correct |
15 |
Correct |
147 ms |
215160 KB |
Output is correct |
16 |
Correct |
146 ms |
214776 KB |
Output is correct |
17 |
Correct |
167 ms |
227064 KB |
Output is correct |
18 |
Correct |
166 ms |
227196 KB |
Output is correct |
19 |
Correct |
169 ms |
227064 KB |
Output is correct |
20 |
Correct |
164 ms |
225656 KB |
Output is correct |
21 |
Correct |
157 ms |
225784 KB |
Output is correct |
22 |
Correct |
159 ms |
225656 KB |
Output is correct |
23 |
Correct |
169 ms |
225784 KB |
Output is correct |
24 |
Correct |
158 ms |
222968 KB |
Output is correct |
25 |
Correct |
446 ms |
304376 KB |
Output is correct |
26 |
Correct |
469 ms |
304504 KB |
Output is correct |
27 |
Correct |
455 ms |
304376 KB |
Output is correct |
28 |
Correct |
297 ms |
281968 KB |
Output is correct |
29 |
Correct |
301 ms |
282648 KB |
Output is correct |
30 |
Correct |
334 ms |
282616 KB |
Output is correct |
31 |
Correct |
299 ms |
283000 KB |
Output is correct |
32 |
Correct |
301 ms |
281976 KB |
Output is correct |
33 |
Runtime error |
438 ms |
443256 KB |
Execution killed with signal 11 |
34 |
Halted |
0 ms |
0 KB |
- |