#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
void mnn(int &a, int b) {
if(a > b) a = b;
}
void mxx(int &a, int b) {
if(a < b) a = b;
}
const int mxn = 2510;
int a[mxn][mxn];
vector<pair<int, int>> h[mxn][mxn], v[mxn][mxn];
void addHor(int i, int l, int r) {
h[i][l].eb(r - l + 1, 1);
}
void addVer(int j, int l, int r) {
v[l][j].eb(r - l + 1, 1);
}
long long count_rectangles(vector<vector<int>> A) {
int n = A.size(), m = A[0].size();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] = A[i - 1][j - 1];
}
}
for(int i = 1; i <= n; i++) {
vector<int> v;
for(int j = 1; j <= m; j++) {
while(v.size() && a[i][v.back()] < a[i][j]) v.pop_back();
if(v.size() && a[i][v.back()] > a[i][j] && v.back() + 1 <= j - 1) {
addHor(i, v.back() + 1, j - 1);
}
v.pb(j);
}
v.clear();
for(int j = m; j >= 1; j--) {
while(v.size() && a[i][v.back()] < a[i][j]) v.pop_back();
if(v.size() && a[i][v.back()] >= a[i][j] && v.back() - 1 >= j + 1) {
addHor(i, j + 1, v.back() - 1);
}
v.pb(j);
}
}
for(int j = 1; j <= m; j++) {
vector<int> v;
for(int i = 1; i <= n; i++) {
while(v.size() && a[v.back()][j] < a[i][j]) v.pop_back();
if(v.size() && a[v.back()][j] > a[i][j] && v.back() + 1 <= i - 1) {
addVer(j, v.back() + 1, i - 1);
}
v.pb(i);
}
v.clear();
for(int i = n; i >= 1; i--) {
while(v.size() && a[v.back()][j] < a[i][j]) v.pop_back();
if(v.size() && a[v.back()][j] >= a[i][j] && v.back() - 1 >= i + 1) {
addVer(j, i + 1, v.back() - 1);
}
v.pb(i);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sort(all(h[i][j]));
sort(all(v[i][j]));
}
}
for(int i = n; i >= 1; i--) {
for(int j = 1; j <= m; j++) {
int p = 0;
for(int k = 0; k < h[i][j].size(); k++) {
while(p < h[i + 1][j].size() && h[i + 1][j][p].ff < h[i][j][k].ff) p++;
if(p < h[i + 1][j].size() && h[i + 1][j][p].ff == h[i][j][k].ff) h[i][j][k].ss = h[i + 1][j][p].ss + 1;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 1; j--) {
int p = 0;
for(int k = 0; k < v[i][j].size(); k++) {
while(p < v[i][j + 1].size() && v[i][j + 1][p].ff < v[i][j][k].ff) p++;
if(p < v[i][j + 1].size() && v[i][j + 1][p].ff == v[i][j][k].ff) v[i][j][k].ss = v[i][j + 1][p].ss + 1;
}
}
}
long long ans = 0;
for(int i = 2; i < n; i++) {
for(int j = 2; j < m; j++) {
for(auto i1 : h[i][j]) {
for(auto i2 : v[i][j]) {
if(i1.ff <= i2.ss && i1.ss >= i2.ff) ans++;
}
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int k = 0; k < h[i][j].size(); k++) {
| ~~^~~~~~~~~~~~~~~~
rect.cpp:99:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | while(p < h[i + 1][j].size() && h[i + 1][j][p].ff < h[i][j][k].ff) p++;
| ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:100:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if(p < h[i + 1][j].size() && h[i + 1][j][p].ff == h[i][j][k].ff) h[i][j][k].ss = h[i + 1][j][p].ss + 1;
| ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int k = 0; k < v[i][j].size(); k++) {
| ~~^~~~~~~~~~~~~~~~
rect.cpp:109:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while(p < v[i][j + 1].size() && v[i][j + 1][p].ff < v[i][j][k].ff) p++;
| ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:110:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | if(p < v[i][j + 1].size() && v[i][j + 1][p].ff == v[i][j][k].ff) v[i][j][k].ss = v[i][j + 1][p].ss + 1;
| ~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
296132 KB |
Output is correct |
2 |
Correct |
121 ms |
296284 KB |
Output is correct |
3 |
Correct |
119 ms |
296288 KB |
Output is correct |
4 |
Correct |
203 ms |
296272 KB |
Output is correct |
5 |
Correct |
125 ms |
296256 KB |
Output is correct |
6 |
Correct |
126 ms |
296228 KB |
Output is correct |
7 |
Correct |
123 ms |
296252 KB |
Output is correct |
8 |
Correct |
127 ms |
296140 KB |
Output is correct |
9 |
Correct |
130 ms |
296272 KB |
Output is correct |
10 |
Correct |
126 ms |
296256 KB |
Output is correct |
11 |
Correct |
130 ms |
296244 KB |
Output is correct |
12 |
Correct |
134 ms |
296256 KB |
Output is correct |
13 |
Correct |
135 ms |
296180 KB |
Output is correct |
14 |
Correct |
141 ms |
296200 KB |
Output is correct |
15 |
Correct |
129 ms |
296156 KB |
Output is correct |
16 |
Correct |
129 ms |
296072 KB |
Output is correct |
17 |
Correct |
129 ms |
296120 KB |
Output is correct |
18 |
Correct |
140 ms |
296124 KB |
Output is correct |
19 |
Correct |
131 ms |
296372 KB |
Output is correct |
20 |
Correct |
128 ms |
296304 KB |
Output is correct |
21 |
Correct |
122 ms |
296176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
296132 KB |
Output is correct |
2 |
Correct |
121 ms |
296284 KB |
Output is correct |
3 |
Correct |
119 ms |
296288 KB |
Output is correct |
4 |
Correct |
203 ms |
296272 KB |
Output is correct |
5 |
Correct |
125 ms |
296256 KB |
Output is correct |
6 |
Correct |
126 ms |
296228 KB |
Output is correct |
7 |
Correct |
123 ms |
296252 KB |
Output is correct |
8 |
Correct |
127 ms |
296140 KB |
Output is correct |
9 |
Correct |
130 ms |
296272 KB |
Output is correct |
10 |
Correct |
126 ms |
296256 KB |
Output is correct |
11 |
Correct |
130 ms |
296244 KB |
Output is correct |
12 |
Correct |
134 ms |
296256 KB |
Output is correct |
13 |
Correct |
135 ms |
296180 KB |
Output is correct |
14 |
Correct |
141 ms |
296200 KB |
Output is correct |
15 |
Correct |
129 ms |
296156 KB |
Output is correct |
16 |
Correct |
129 ms |
296072 KB |
Output is correct |
17 |
Correct |
129 ms |
296120 KB |
Output is correct |
18 |
Correct |
140 ms |
296124 KB |
Output is correct |
19 |
Correct |
131 ms |
296372 KB |
Output is correct |
20 |
Correct |
128 ms |
296304 KB |
Output is correct |
21 |
Correct |
122 ms |
296176 KB |
Output is correct |
22 |
Correct |
136 ms |
296916 KB |
Output is correct |
23 |
Correct |
130 ms |
296924 KB |
Output is correct |
24 |
Correct |
129 ms |
297008 KB |
Output is correct |
25 |
Correct |
152 ms |
296672 KB |
Output is correct |
26 |
Correct |
158 ms |
296732 KB |
Output is correct |
27 |
Correct |
148 ms |
296836 KB |
Output is correct |
28 |
Correct |
170 ms |
296780 KB |
Output is correct |
29 |
Correct |
143 ms |
296576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
296132 KB |
Output is correct |
2 |
Correct |
121 ms |
296284 KB |
Output is correct |
3 |
Correct |
119 ms |
296288 KB |
Output is correct |
4 |
Correct |
203 ms |
296272 KB |
Output is correct |
5 |
Correct |
125 ms |
296256 KB |
Output is correct |
6 |
Correct |
126 ms |
296228 KB |
Output is correct |
7 |
Correct |
123 ms |
296252 KB |
Output is correct |
8 |
Correct |
127 ms |
296140 KB |
Output is correct |
9 |
Correct |
130 ms |
296272 KB |
Output is correct |
10 |
Correct |
126 ms |
296256 KB |
Output is correct |
11 |
Correct |
130 ms |
296244 KB |
Output is correct |
12 |
Correct |
134 ms |
296256 KB |
Output is correct |
13 |
Correct |
135 ms |
296180 KB |
Output is correct |
14 |
Correct |
141 ms |
296200 KB |
Output is correct |
15 |
Correct |
129 ms |
296156 KB |
Output is correct |
16 |
Correct |
129 ms |
296072 KB |
Output is correct |
17 |
Correct |
136 ms |
296916 KB |
Output is correct |
18 |
Correct |
130 ms |
296924 KB |
Output is correct |
19 |
Correct |
129 ms |
297008 KB |
Output is correct |
20 |
Correct |
152 ms |
296672 KB |
Output is correct |
21 |
Correct |
158 ms |
296732 KB |
Output is correct |
22 |
Correct |
148 ms |
296836 KB |
Output is correct |
23 |
Correct |
170 ms |
296780 KB |
Output is correct |
24 |
Correct |
143 ms |
296576 KB |
Output is correct |
25 |
Correct |
129 ms |
296120 KB |
Output is correct |
26 |
Correct |
140 ms |
296124 KB |
Output is correct |
27 |
Correct |
131 ms |
296372 KB |
Output is correct |
28 |
Correct |
128 ms |
296304 KB |
Output is correct |
29 |
Correct |
122 ms |
296176 KB |
Output is correct |
30 |
Correct |
136 ms |
300140 KB |
Output is correct |
31 |
Correct |
142 ms |
300072 KB |
Output is correct |
32 |
Correct |
155 ms |
300236 KB |
Output is correct |
33 |
Correct |
148 ms |
298300 KB |
Output is correct |
34 |
Correct |
174 ms |
299004 KB |
Output is correct |
35 |
Correct |
153 ms |
299204 KB |
Output is correct |
36 |
Correct |
156 ms |
299080 KB |
Output is correct |
37 |
Correct |
158 ms |
299072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
296132 KB |
Output is correct |
2 |
Correct |
121 ms |
296284 KB |
Output is correct |
3 |
Correct |
119 ms |
296288 KB |
Output is correct |
4 |
Correct |
203 ms |
296272 KB |
Output is correct |
5 |
Correct |
125 ms |
296256 KB |
Output is correct |
6 |
Correct |
126 ms |
296228 KB |
Output is correct |
7 |
Correct |
123 ms |
296252 KB |
Output is correct |
8 |
Correct |
127 ms |
296140 KB |
Output is correct |
9 |
Correct |
130 ms |
296272 KB |
Output is correct |
10 |
Correct |
126 ms |
296256 KB |
Output is correct |
11 |
Correct |
130 ms |
296244 KB |
Output is correct |
12 |
Correct |
134 ms |
296256 KB |
Output is correct |
13 |
Correct |
135 ms |
296180 KB |
Output is correct |
14 |
Correct |
141 ms |
296200 KB |
Output is correct |
15 |
Correct |
129 ms |
296156 KB |
Output is correct |
16 |
Correct |
129 ms |
296072 KB |
Output is correct |
17 |
Correct |
136 ms |
296916 KB |
Output is correct |
18 |
Correct |
130 ms |
296924 KB |
Output is correct |
19 |
Correct |
129 ms |
297008 KB |
Output is correct |
20 |
Correct |
152 ms |
296672 KB |
Output is correct |
21 |
Correct |
158 ms |
296732 KB |
Output is correct |
22 |
Correct |
148 ms |
296836 KB |
Output is correct |
23 |
Correct |
170 ms |
296780 KB |
Output is correct |
24 |
Correct |
143 ms |
296576 KB |
Output is correct |
25 |
Correct |
136 ms |
300140 KB |
Output is correct |
26 |
Correct |
142 ms |
300072 KB |
Output is correct |
27 |
Correct |
155 ms |
300236 KB |
Output is correct |
28 |
Correct |
148 ms |
298300 KB |
Output is correct |
29 |
Correct |
174 ms |
299004 KB |
Output is correct |
30 |
Correct |
153 ms |
299204 KB |
Output is correct |
31 |
Correct |
156 ms |
299080 KB |
Output is correct |
32 |
Correct |
158 ms |
299072 KB |
Output is correct |
33 |
Correct |
129 ms |
296120 KB |
Output is correct |
34 |
Correct |
140 ms |
296124 KB |
Output is correct |
35 |
Correct |
131 ms |
296372 KB |
Output is correct |
36 |
Correct |
128 ms |
296304 KB |
Output is correct |
37 |
Correct |
122 ms |
296176 KB |
Output is correct |
38 |
Correct |
198 ms |
323252 KB |
Output is correct |
39 |
Correct |
205 ms |
318440 KB |
Output is correct |
40 |
Correct |
193 ms |
318464 KB |
Output is correct |
41 |
Correct |
250 ms |
313656 KB |
Output is correct |
42 |
Correct |
219 ms |
338612 KB |
Output is correct |
43 |
Correct |
220 ms |
338608 KB |
Output is correct |
44 |
Correct |
225 ms |
338892 KB |
Output is correct |
45 |
Correct |
220 ms |
336240 KB |
Output is correct |
46 |
Correct |
213 ms |
313416 KB |
Output is correct |
47 |
Correct |
234 ms |
315972 KB |
Output is correct |
48 |
Correct |
264 ms |
324428 KB |
Output is correct |
49 |
Correct |
275 ms |
326580 KB |
Output is correct |
50 |
Correct |
214 ms |
312764 KB |
Output is correct |
51 |
Correct |
211 ms |
311228 KB |
Output is correct |
52 |
Correct |
268 ms |
324052 KB |
Output is correct |
53 |
Correct |
270 ms |
325140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
296532 KB |
Output is correct |
2 |
Correct |
149 ms |
296580 KB |
Output is correct |
3 |
Correct |
145 ms |
296228 KB |
Output is correct |
4 |
Correct |
143 ms |
296160 KB |
Output is correct |
5 |
Correct |
148 ms |
296492 KB |
Output is correct |
6 |
Correct |
149 ms |
296404 KB |
Output is correct |
7 |
Correct |
146 ms |
296472 KB |
Output is correct |
8 |
Correct |
147 ms |
296348 KB |
Output is correct |
9 |
Correct |
144 ms |
296368 KB |
Output is correct |
10 |
Correct |
147 ms |
296264 KB |
Output is correct |
11 |
Correct |
146 ms |
296368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
296120 KB |
Output is correct |
2 |
Correct |
140 ms |
296124 KB |
Output is correct |
3 |
Correct |
131 ms |
296372 KB |
Output is correct |
4 |
Correct |
128 ms |
296304 KB |
Output is correct |
5 |
Correct |
122 ms |
296176 KB |
Output is correct |
6 |
Correct |
141 ms |
296196 KB |
Output is correct |
7 |
Correct |
494 ms |
381228 KB |
Output is correct |
8 |
Correct |
924 ms |
478952 KB |
Output is correct |
9 |
Correct |
940 ms |
479756 KB |
Output is correct |
10 |
Correct |
931 ms |
479880 KB |
Output is correct |
11 |
Correct |
259 ms |
338564 KB |
Output is correct |
12 |
Correct |
378 ms |
378228 KB |
Output is correct |
13 |
Correct |
396 ms |
382096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
296132 KB |
Output is correct |
2 |
Correct |
121 ms |
296284 KB |
Output is correct |
3 |
Correct |
119 ms |
296288 KB |
Output is correct |
4 |
Correct |
203 ms |
296272 KB |
Output is correct |
5 |
Correct |
125 ms |
296256 KB |
Output is correct |
6 |
Correct |
126 ms |
296228 KB |
Output is correct |
7 |
Correct |
123 ms |
296252 KB |
Output is correct |
8 |
Correct |
127 ms |
296140 KB |
Output is correct |
9 |
Correct |
130 ms |
296272 KB |
Output is correct |
10 |
Correct |
126 ms |
296256 KB |
Output is correct |
11 |
Correct |
130 ms |
296244 KB |
Output is correct |
12 |
Correct |
134 ms |
296256 KB |
Output is correct |
13 |
Correct |
135 ms |
296180 KB |
Output is correct |
14 |
Correct |
141 ms |
296200 KB |
Output is correct |
15 |
Correct |
129 ms |
296156 KB |
Output is correct |
16 |
Correct |
129 ms |
296072 KB |
Output is correct |
17 |
Correct |
136 ms |
296916 KB |
Output is correct |
18 |
Correct |
130 ms |
296924 KB |
Output is correct |
19 |
Correct |
129 ms |
297008 KB |
Output is correct |
20 |
Correct |
152 ms |
296672 KB |
Output is correct |
21 |
Correct |
158 ms |
296732 KB |
Output is correct |
22 |
Correct |
148 ms |
296836 KB |
Output is correct |
23 |
Correct |
170 ms |
296780 KB |
Output is correct |
24 |
Correct |
143 ms |
296576 KB |
Output is correct |
25 |
Correct |
136 ms |
300140 KB |
Output is correct |
26 |
Correct |
142 ms |
300072 KB |
Output is correct |
27 |
Correct |
155 ms |
300236 KB |
Output is correct |
28 |
Correct |
148 ms |
298300 KB |
Output is correct |
29 |
Correct |
174 ms |
299004 KB |
Output is correct |
30 |
Correct |
153 ms |
299204 KB |
Output is correct |
31 |
Correct |
156 ms |
299080 KB |
Output is correct |
32 |
Correct |
158 ms |
299072 KB |
Output is correct |
33 |
Correct |
198 ms |
323252 KB |
Output is correct |
34 |
Correct |
205 ms |
318440 KB |
Output is correct |
35 |
Correct |
193 ms |
318464 KB |
Output is correct |
36 |
Correct |
250 ms |
313656 KB |
Output is correct |
37 |
Correct |
219 ms |
338612 KB |
Output is correct |
38 |
Correct |
220 ms |
338608 KB |
Output is correct |
39 |
Correct |
225 ms |
338892 KB |
Output is correct |
40 |
Correct |
220 ms |
336240 KB |
Output is correct |
41 |
Correct |
213 ms |
313416 KB |
Output is correct |
42 |
Correct |
234 ms |
315972 KB |
Output is correct |
43 |
Correct |
264 ms |
324428 KB |
Output is correct |
44 |
Correct |
275 ms |
326580 KB |
Output is correct |
45 |
Correct |
214 ms |
312764 KB |
Output is correct |
46 |
Correct |
211 ms |
311228 KB |
Output is correct |
47 |
Correct |
268 ms |
324052 KB |
Output is correct |
48 |
Correct |
270 ms |
325140 KB |
Output is correct |
49 |
Correct |
148 ms |
296532 KB |
Output is correct |
50 |
Correct |
149 ms |
296580 KB |
Output is correct |
51 |
Correct |
145 ms |
296228 KB |
Output is correct |
52 |
Correct |
143 ms |
296160 KB |
Output is correct |
53 |
Correct |
148 ms |
296492 KB |
Output is correct |
54 |
Correct |
149 ms |
296404 KB |
Output is correct |
55 |
Correct |
146 ms |
296472 KB |
Output is correct |
56 |
Correct |
147 ms |
296348 KB |
Output is correct |
57 |
Correct |
144 ms |
296368 KB |
Output is correct |
58 |
Correct |
147 ms |
296264 KB |
Output is correct |
59 |
Correct |
146 ms |
296368 KB |
Output is correct |
60 |
Correct |
141 ms |
296196 KB |
Output is correct |
61 |
Correct |
494 ms |
381228 KB |
Output is correct |
62 |
Correct |
924 ms |
478952 KB |
Output is correct |
63 |
Correct |
940 ms |
479756 KB |
Output is correct |
64 |
Correct |
931 ms |
479880 KB |
Output is correct |
65 |
Correct |
259 ms |
338564 KB |
Output is correct |
66 |
Correct |
378 ms |
378228 KB |
Output is correct |
67 |
Correct |
396 ms |
382096 KB |
Output is correct |
68 |
Correct |
129 ms |
296120 KB |
Output is correct |
69 |
Correct |
140 ms |
296124 KB |
Output is correct |
70 |
Correct |
131 ms |
296372 KB |
Output is correct |
71 |
Correct |
128 ms |
296304 KB |
Output is correct |
72 |
Correct |
122 ms |
296176 KB |
Output is correct |
73 |
Correct |
1000 ms |
611980 KB |
Output is correct |
74 |
Correct |
1037 ms |
545208 KB |
Output is correct |
75 |
Correct |
732 ms |
545092 KB |
Output is correct |
76 |
Correct |
3896 ms |
478052 KB |
Output is correct |
77 |
Correct |
2645 ms |
801232 KB |
Output is correct |
78 |
Correct |
1196 ms |
492372 KB |
Output is correct |
79 |
Correct |
1259 ms |
520804 KB |
Output is correct |
80 |
Correct |
1828 ms |
623404 KB |
Output is correct |
81 |
Correct |
1188 ms |
508820 KB |
Output is correct |
82 |
Correct |
1580 ms |
584856 KB |
Output is correct |
83 |
Correct |
1917 ms |
650808 KB |
Output is correct |
84 |
Correct |
1108 ms |
490788 KB |
Output is correct |
85 |
Correct |
1845 ms |
634564 KB |
Output is correct |
86 |
Correct |
1842 ms |
624428 KB |
Output is correct |
87 |
Correct |
947 ms |
613452 KB |
Output is correct |
88 |
Correct |
2317 ms |
802564 KB |
Output is correct |
89 |
Correct |
1839 ms |
808748 KB |
Output is correct |
90 |
Correct |
1809 ms |
808264 KB |
Output is correct |