#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
// #define ll long long
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ss second
#define int short
const int N = 2600, K = 20;
long long count_rectangles(std::vector<std::vector<int32_t> > a) {
int n = a.size();
int m = a[0].size();
if(n < 3 || m < 3){
return 0;
}
long long ans = 0;
vector<vector<int>> L, R, D, U;
L.resize(n, vector<int>(m));
R.resize(n, vector<int>(m));
D.resize(n, vector<int>(m));
U.resize(n, vector<int>(m));
for(int i = 0; i < n; ++i){
vector<int> q;
for(int j = 0; j < m; ++j){
while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
if(q.empty()){
L[i][j] = -1;
}else{
L[i][j] = q.back();
}
q.pb(j);
}
q.clear();
for(int j = m - 1; j >= 0; --j){
while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
if(q.empty()){
R[i][j] = m;
}else{
R[i][j] = q.back();
}
q.pb(j);
}
}
for(int j = 0; j < m; ++j){
vector<int> q;
for(int i = 0; i < n; ++i){
while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
if(q.empty()){
U[i][j] = -1;
}else{
U[i][j] = q.back();
}
q.pb(i);
}
q.clear();
for(int i = n - 1; i >= 0; --i){
while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
if(q.empty()){
D[i][j] = n;
}else{
D[i][j] = q.back();
}
q.pb(i);
}
}
vector<vector<vector<int>>> rangesL(n, vector<vector<int>>(m));
vector<vector<vector<int>>> rangesU(n, vector<vector<int>>(m));
for(int i = 1; i + 1 < n; ++i){
for(int j = 1; j + 1 < m; ++j){
int l = L[i][j], r = R[i][j];
while(l > -1 && r < m){
// cout << i << ' ' << j << ' ' << l + 1 << ' ' << r - 1 << '\n';
rangesL[i][r - 1].pb(l + 1);
if(a[i][l] < a[i][r]){
l = L[i][l];
}else if(a[i][l] > a[i][r]){
r = R[i][r];
}else{
l = L[i][l];
r = R[i][r];
}
}
}
}
for(int j = 1; j + 1 < m; ++j){
for(int i = 1; i + 1 < n; ++i){
int l = U[i][j], r = D[i][j];
while(l > -1 && r < n){
// cout << l << ' ' << r << ' ' << i << ' ' << j << '\n';
rangesU[r - 1][j].pb(l + 1);
if(a[l][j] < a[r][j]){
l = U[l][j];
}else if(a[l][j] > a[r][j]){
r = D[r][j];
}else{
l = U[l][j];
r = D[r][j];
}
}
}
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << L[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << R[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << U[i][j] << ' ';en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << D[i][j] << ' ';en;
// }
vector<vector<vector<int>>> colranges(max(n,m), vector<vector<int>>(max(n,m)));
vector<vector<vector<int>>> rowranges(max(n,m), vector<vector<int>>(max(n,m)));
// cout << "wtf" << endl;
for(int i = 1; i + 1 < n; ++i){
for(int j = 1; j + 1 < m; ++j){
sort(all(rangesL[i][j]), greater<int>());
rangesL[i][j].erase(unique(all(rangesL[i][j])), rangesL[i][j].end());
sort(all(rangesU[i][j]), greater<int>());
rangesU[i][j].erase(unique(all(rangesU[i][j])), rangesU[i][j].end());
int ls = rangesL[i][j].size();
int us = rangesU[i][j].size();
// cout << i << ' ' << j << '\n';
// cout << "L: ";
for(int x = 0; x < ls; ++x){
if(colranges[j][rangesL[i][j][x]].size() && colranges[j][rangesL[i][j][x]].back() < i - 1){
colranges[j][rangesL[i][j][x]].clear();
}
colranges[j][rangesL[i][j][x]].pb(i);
// cout << rangesL[i][j][x] << ' ';
}
// cout << "R: ";
for(int x = 0; x < us; ++x){
if(rowranges[i][rangesU[i][j][x]].size() && rowranges[i][rangesU[i][j][x]].back() < j - 1){
rowranges[i][rangesU[i][j][x]].clear();
}
rowranges[i][rangesU[i][j][x]].pb(j);
// cout << rangesU[i][j][x] << ' ';
}
// en;en;
for(int y = us - 1; y >= 0; --y){
int u = rangesU[i][j][y];
for(int x = ls - 1; x >= 0; --x){
int l = rangesL[i][j][x];
// cout << i << ' ' << j << ' ' << u << ' ' << l << '\n';
// cout << (rowranges[i][u].size() >= j - l + 1 && rowranges[i][u][int(rowranges[i][u].size()) - (j - l + 1)] == l) << ' ' <<
// (colranges[j][l].size() >= i - u + 1 && colranges[j][l][int(colranges[j][l].size()) - (i - u + 1)] == u) << '\n';
if(rowranges[i][u].size() >= j - l + 1
&& colranges[j][l].size() >= i - u + 1){
++ans;
}
}
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:171:32: warning: comparison of integer expressions of different signedness: 'std::vector<short int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
171 | if(rowranges[i][u].size() >= j - l + 1
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
rect.cpp:172:33: warning: comparison of integer expressions of different signedness: 'std::vector<short int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
172 | && colranges[j][l].size() >= i - u + 1){
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
7 ms |
2396 KB |
Output is correct |
23 |
Correct |
7 ms |
2396 KB |
Output is correct |
24 |
Correct |
7 ms |
2396 KB |
Output is correct |
25 |
Correct |
1 ms |
1116 KB |
Output is correct |
26 |
Correct |
3 ms |
1368 KB |
Output is correct |
27 |
Correct |
3 ms |
1372 KB |
Output is correct |
28 |
Correct |
3 ms |
1372 KB |
Output is correct |
29 |
Correct |
1 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
2396 KB |
Output is correct |
18 |
Correct |
7 ms |
2396 KB |
Output is correct |
19 |
Correct |
7 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
3 ms |
1368 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1372 KB |
Output is correct |
24 |
Correct |
1 ms |
856 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
193 ms |
21672 KB |
Output is correct |
31 |
Correct |
196 ms |
21708 KB |
Output is correct |
32 |
Correct |
193 ms |
21660 KB |
Output is correct |
33 |
Correct |
7 ms |
5720 KB |
Output is correct |
34 |
Correct |
19 ms |
7260 KB |
Output is correct |
35 |
Correct |
18 ms |
7196 KB |
Output is correct |
36 |
Correct |
17 ms |
7004 KB |
Output is correct |
37 |
Correct |
19 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
2396 KB |
Output is correct |
18 |
Correct |
7 ms |
2396 KB |
Output is correct |
19 |
Correct |
7 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
3 ms |
1368 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1372 KB |
Output is correct |
24 |
Correct |
1 ms |
856 KB |
Output is correct |
25 |
Correct |
193 ms |
21672 KB |
Output is correct |
26 |
Correct |
196 ms |
21708 KB |
Output is correct |
27 |
Correct |
193 ms |
21660 KB |
Output is correct |
28 |
Correct |
7 ms |
5720 KB |
Output is correct |
29 |
Correct |
19 ms |
7260 KB |
Output is correct |
30 |
Correct |
18 ms |
7196 KB |
Output is correct |
31 |
Correct |
17 ms |
7004 KB |
Output is correct |
32 |
Correct |
19 ms |
7004 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
3099 ms |
295920 KB |
Output is correct |
39 |
Correct |
2270 ms |
349120 KB |
Output is correct |
40 |
Correct |
2360 ms |
349060 KB |
Output is correct |
41 |
Correct |
1503 ms |
401436 KB |
Output is correct |
42 |
Execution timed out |
5059 ms |
727108 KB |
Time limit exceeded |
43 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
300976 KB |
Output is correct |
2 |
Correct |
148 ms |
219052 KB |
Output is correct |
3 |
Correct |
122 ms |
294484 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
106 ms |
294744 KB |
Output is correct |
6 |
Correct |
105 ms |
294740 KB |
Output is correct |
7 |
Correct |
104 ms |
294740 KB |
Output is correct |
8 |
Correct |
108 ms |
294736 KB |
Output is correct |
9 |
Correct |
110 ms |
294736 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
551 ms |
479056 KB |
Output is correct |
8 |
Correct |
1098 ms |
782876 KB |
Output is correct |
9 |
Correct |
1113 ms |
785236 KB |
Output is correct |
10 |
Correct |
1115 ms |
785492 KB |
Output is correct |
11 |
Correct |
280 ms |
487508 KB |
Output is correct |
12 |
Correct |
444 ms |
662080 KB |
Output is correct |
13 |
Correct |
469 ms |
686164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
2396 KB |
Output is correct |
18 |
Correct |
7 ms |
2396 KB |
Output is correct |
19 |
Correct |
7 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
3 ms |
1368 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1372 KB |
Output is correct |
24 |
Correct |
1 ms |
856 KB |
Output is correct |
25 |
Correct |
193 ms |
21672 KB |
Output is correct |
26 |
Correct |
196 ms |
21708 KB |
Output is correct |
27 |
Correct |
193 ms |
21660 KB |
Output is correct |
28 |
Correct |
7 ms |
5720 KB |
Output is correct |
29 |
Correct |
19 ms |
7260 KB |
Output is correct |
30 |
Correct |
18 ms |
7196 KB |
Output is correct |
31 |
Correct |
17 ms |
7004 KB |
Output is correct |
32 |
Correct |
19 ms |
7004 KB |
Output is correct |
33 |
Correct |
3099 ms |
295920 KB |
Output is correct |
34 |
Correct |
2270 ms |
349120 KB |
Output is correct |
35 |
Correct |
2360 ms |
349060 KB |
Output is correct |
36 |
Correct |
1503 ms |
401436 KB |
Output is correct |
37 |
Execution timed out |
5059 ms |
727108 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |