#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2500 + 1;
vector<int> row_conds[MAX_N][MAX_N];
vector<int> col_conds[MAX_N][MAX_N];
pii row_range[MAX_N][MAX_N]; // in the same row
pii col_range[MAX_N][MAX_N]; // in the same col
ll count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
memset(row_range, -1, sizeof row_range);
memset(col_range, -1, sizeof col_range);
for (int i=1; i+1<n; ++i) {
vector<pii> st;
for (int j=0; j<m; ++j) {
while (!st.empty() && st.back().first < a[i][j]) {
row_range[i][st.back().second].second = j-1;
st.pop_back();
}
st.push_back({ a[i][j], j });
}
st.clear();
for (int j=m-1; j>=0; --j) {
while (!st.empty() && st.back().first < a[i][j]) {
row_range[i][st.back().second].first = j+1;
st.pop_back();
}
st.push_back({ a[i][j], j });
}
}
for (int i=1; i+1<m; ++i) {
vector<pii> st;
for (int j=0; j<n; ++j) {
while (!st.empty() && st.back().first < a[j][i]) {
col_range[st.back().second][i].second = j-1;
st.pop_back();
}
st.push_back({ a[j][i], j });
}
st.clear();
for (int j=n-1; j>=0; --j) {
while (!st.empty() && st.back().first < a[j][i]) {
col_range[st.back().second][i].first = j+1;
st.pop_back();
}
st.push_back({ a[j][i], j });
}
}
for (int i=1; i+1<n; ++i) {
for (int j=1; j+1<m; ++j) {
auto[a, b] = row_range[i][j];
if (a != -1 && b != -1) row_conds[a][b].push_back(i);
}
}
for (int j=1; j+1<m; ++j) {
for (int i=1; i+1<n; ++i) {
auto[c, d] = col_range[i][j];
if (c != -1 && d != -1) col_conds[c][d].push_back(j);
}
}
for (int i=0; i<MAX_N; ++i) {
for (int j=i; j<MAX_N; ++j) {
row_conds[i][j].erase(unique(row_conds[i][j].begin(), row_conds[i][j].end()), row_conds[i][j].end());
col_conds[i][j].erase(unique(col_conds[i][j].begin(), col_conds[i][j].end()), col_conds[i][j].end());
}
}
ll ans = 0;
vector<pii> cands;
for (int i=1; i+1<n; ++i) {
for (int j=1; j+1<m; ++j) {
auto[a, b] = row_range[i][j];
auto[c, d] = col_range[i][j];
if (a != -1 && b != -1 && c != -1 && d != -1) cands.push_back({ a * MAX_N + b, c * MAX_N + d });
}
}
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
for (auto[a, c]: cands) {
auto b = a % MAX_N, d = c % MAX_N;
a /= MAX_N, c /= MAX_N;
auto row_lb = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), c);
auto row_ub = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), d);
auto col_lb = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), a);
auto col_ub = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), b);
// cout << i << ' ' << j << ' ' << *row_lb << ' ' << *row_ub << ' ' << *col_lb << ' ' << *col_ub << endl;
if (*row_lb == c && *row_ub == d && row_ub-row_lb == d-c
&& *col_lb == a && *col_ub == b && col_ub-col_lb == b-a) ans++;
}
// for (int i=1; i+1<n; ++i) {
// for (int j=1; j+1<m; ++j) {
// auto[a, b] = row_range[i][j];
// auto[c, d] = col_range[i][j];
// if (a != -1 && b != -1 && c != -1 && d != -1) {
// }
// }
// }
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
392088 KB |
Output is correct |
2 |
Correct |
195 ms |
392012 KB |
Output is correct |
3 |
Correct |
190 ms |
392012 KB |
Output is correct |
4 |
Correct |
188 ms |
392004 KB |
Output is correct |
5 |
Correct |
192 ms |
392012 KB |
Output is correct |
6 |
Correct |
191 ms |
391916 KB |
Output is correct |
7 |
Correct |
195 ms |
391992 KB |
Output is correct |
8 |
Correct |
200 ms |
391980 KB |
Output is correct |
9 |
Correct |
194 ms |
391916 KB |
Output is correct |
10 |
Correct |
189 ms |
392128 KB |
Output is correct |
11 |
Correct |
196 ms |
392032 KB |
Output is correct |
12 |
Correct |
202 ms |
391924 KB |
Output is correct |
13 |
Correct |
193 ms |
391984 KB |
Output is correct |
14 |
Correct |
194 ms |
391908 KB |
Output is correct |
15 |
Correct |
203 ms |
392060 KB |
Output is correct |
16 |
Correct |
200 ms |
391892 KB |
Output is correct |
17 |
Correct |
207 ms |
391920 KB |
Output is correct |
18 |
Correct |
211 ms |
391976 KB |
Output is correct |
19 |
Correct |
201 ms |
392008 KB |
Output is correct |
20 |
Correct |
203 ms |
391900 KB |
Output is correct |
21 |
Correct |
199 ms |
391944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
392088 KB |
Output is correct |
2 |
Correct |
195 ms |
392012 KB |
Output is correct |
3 |
Correct |
190 ms |
392012 KB |
Output is correct |
4 |
Correct |
188 ms |
392004 KB |
Output is correct |
5 |
Correct |
192 ms |
392012 KB |
Output is correct |
6 |
Correct |
191 ms |
391916 KB |
Output is correct |
7 |
Correct |
195 ms |
391992 KB |
Output is correct |
8 |
Correct |
200 ms |
391980 KB |
Output is correct |
9 |
Correct |
194 ms |
391916 KB |
Output is correct |
10 |
Correct |
189 ms |
392128 KB |
Output is correct |
11 |
Correct |
196 ms |
392032 KB |
Output is correct |
12 |
Correct |
202 ms |
391924 KB |
Output is correct |
13 |
Correct |
193 ms |
391984 KB |
Output is correct |
14 |
Correct |
194 ms |
391908 KB |
Output is correct |
15 |
Correct |
203 ms |
392060 KB |
Output is correct |
16 |
Correct |
200 ms |
391892 KB |
Output is correct |
17 |
Correct |
207 ms |
391920 KB |
Output is correct |
18 |
Correct |
211 ms |
391976 KB |
Output is correct |
19 |
Correct |
201 ms |
392008 KB |
Output is correct |
20 |
Correct |
203 ms |
391900 KB |
Output is correct |
21 |
Correct |
199 ms |
391944 KB |
Output is correct |
22 |
Correct |
192 ms |
392176 KB |
Output is correct |
23 |
Correct |
199 ms |
392180 KB |
Output is correct |
24 |
Correct |
218 ms |
392208 KB |
Output is correct |
25 |
Correct |
202 ms |
392080 KB |
Output is correct |
26 |
Correct |
223 ms |
392216 KB |
Output is correct |
27 |
Correct |
198 ms |
392392 KB |
Output is correct |
28 |
Correct |
202 ms |
392244 KB |
Output is correct |
29 |
Correct |
214 ms |
392012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
392088 KB |
Output is correct |
2 |
Correct |
195 ms |
392012 KB |
Output is correct |
3 |
Correct |
190 ms |
392012 KB |
Output is correct |
4 |
Correct |
188 ms |
392004 KB |
Output is correct |
5 |
Correct |
192 ms |
392012 KB |
Output is correct |
6 |
Correct |
191 ms |
391916 KB |
Output is correct |
7 |
Correct |
195 ms |
391992 KB |
Output is correct |
8 |
Correct |
200 ms |
391980 KB |
Output is correct |
9 |
Correct |
194 ms |
391916 KB |
Output is correct |
10 |
Correct |
189 ms |
392128 KB |
Output is correct |
11 |
Correct |
196 ms |
392032 KB |
Output is correct |
12 |
Correct |
202 ms |
391924 KB |
Output is correct |
13 |
Correct |
193 ms |
391984 KB |
Output is correct |
14 |
Correct |
194 ms |
391908 KB |
Output is correct |
15 |
Correct |
203 ms |
392060 KB |
Output is correct |
16 |
Correct |
200 ms |
391892 KB |
Output is correct |
17 |
Correct |
192 ms |
392176 KB |
Output is correct |
18 |
Correct |
199 ms |
392180 KB |
Output is correct |
19 |
Correct |
218 ms |
392208 KB |
Output is correct |
20 |
Correct |
202 ms |
392080 KB |
Output is correct |
21 |
Correct |
223 ms |
392216 KB |
Output is correct |
22 |
Correct |
198 ms |
392392 KB |
Output is correct |
23 |
Correct |
202 ms |
392244 KB |
Output is correct |
24 |
Correct |
214 ms |
392012 KB |
Output is correct |
25 |
Correct |
207 ms |
391920 KB |
Output is correct |
26 |
Correct |
211 ms |
391976 KB |
Output is correct |
27 |
Correct |
201 ms |
392008 KB |
Output is correct |
28 |
Correct |
203 ms |
391900 KB |
Output is correct |
29 |
Correct |
199 ms |
391944 KB |
Output is correct |
30 |
Correct |
233 ms |
393592 KB |
Output is correct |
31 |
Correct |
205 ms |
393548 KB |
Output is correct |
32 |
Correct |
222 ms |
393672 KB |
Output is correct |
33 |
Correct |
222 ms |
393368 KB |
Output is correct |
34 |
Correct |
221 ms |
393816 KB |
Output is correct |
35 |
Correct |
220 ms |
393844 KB |
Output is correct |
36 |
Correct |
236 ms |
393708 KB |
Output is correct |
37 |
Correct |
211 ms |
393788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
392088 KB |
Output is correct |
2 |
Correct |
195 ms |
392012 KB |
Output is correct |
3 |
Correct |
190 ms |
392012 KB |
Output is correct |
4 |
Correct |
188 ms |
392004 KB |
Output is correct |
5 |
Correct |
192 ms |
392012 KB |
Output is correct |
6 |
Correct |
191 ms |
391916 KB |
Output is correct |
7 |
Correct |
195 ms |
391992 KB |
Output is correct |
8 |
Correct |
200 ms |
391980 KB |
Output is correct |
9 |
Correct |
194 ms |
391916 KB |
Output is correct |
10 |
Correct |
189 ms |
392128 KB |
Output is correct |
11 |
Correct |
196 ms |
392032 KB |
Output is correct |
12 |
Correct |
202 ms |
391924 KB |
Output is correct |
13 |
Correct |
193 ms |
391984 KB |
Output is correct |
14 |
Correct |
194 ms |
391908 KB |
Output is correct |
15 |
Correct |
203 ms |
392060 KB |
Output is correct |
16 |
Correct |
200 ms |
391892 KB |
Output is correct |
17 |
Correct |
192 ms |
392176 KB |
Output is correct |
18 |
Correct |
199 ms |
392180 KB |
Output is correct |
19 |
Correct |
218 ms |
392208 KB |
Output is correct |
20 |
Correct |
202 ms |
392080 KB |
Output is correct |
21 |
Correct |
223 ms |
392216 KB |
Output is correct |
22 |
Correct |
198 ms |
392392 KB |
Output is correct |
23 |
Correct |
202 ms |
392244 KB |
Output is correct |
24 |
Correct |
214 ms |
392012 KB |
Output is correct |
25 |
Correct |
233 ms |
393592 KB |
Output is correct |
26 |
Correct |
205 ms |
393548 KB |
Output is correct |
27 |
Correct |
222 ms |
393672 KB |
Output is correct |
28 |
Correct |
222 ms |
393368 KB |
Output is correct |
29 |
Correct |
221 ms |
393816 KB |
Output is correct |
30 |
Correct |
220 ms |
393844 KB |
Output is correct |
31 |
Correct |
236 ms |
393708 KB |
Output is correct |
32 |
Correct |
211 ms |
393788 KB |
Output is correct |
33 |
Correct |
207 ms |
391920 KB |
Output is correct |
34 |
Correct |
211 ms |
391976 KB |
Output is correct |
35 |
Correct |
201 ms |
392008 KB |
Output is correct |
36 |
Correct |
203 ms |
391900 KB |
Output is correct |
37 |
Correct |
199 ms |
391944 KB |
Output is correct |
38 |
Correct |
308 ms |
413712 KB |
Output is correct |
39 |
Correct |
266 ms |
413632 KB |
Output is correct |
40 |
Correct |
270 ms |
413920 KB |
Output is correct |
41 |
Correct |
279 ms |
413676 KB |
Output is correct |
42 |
Correct |
386 ms |
408308 KB |
Output is correct |
43 |
Correct |
378 ms |
408304 KB |
Output is correct |
44 |
Correct |
395 ms |
408228 KB |
Output is correct |
45 |
Correct |
376 ms |
407880 KB |
Output is correct |
46 |
Correct |
309 ms |
402204 KB |
Output is correct |
47 |
Correct |
343 ms |
404980 KB |
Output is correct |
48 |
Correct |
435 ms |
408168 KB |
Output is correct |
49 |
Correct |
442 ms |
409124 KB |
Output is correct |
50 |
Correct |
312 ms |
401376 KB |
Output is correct |
51 |
Correct |
299 ms |
401452 KB |
Output is correct |
52 |
Correct |
438 ms |
408312 KB |
Output is correct |
53 |
Correct |
405 ms |
408364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
392148 KB |
Output is correct |
2 |
Correct |
196 ms |
392084 KB |
Output is correct |
3 |
Correct |
203 ms |
392140 KB |
Output is correct |
4 |
Correct |
200 ms |
391980 KB |
Output is correct |
5 |
Correct |
198 ms |
392120 KB |
Output is correct |
6 |
Correct |
196 ms |
392028 KB |
Output is correct |
7 |
Correct |
205 ms |
392112 KB |
Output is correct |
8 |
Correct |
193 ms |
392012 KB |
Output is correct |
9 |
Correct |
192 ms |
392024 KB |
Output is correct |
10 |
Correct |
206 ms |
392016 KB |
Output is correct |
11 |
Correct |
192 ms |
391964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
391920 KB |
Output is correct |
2 |
Correct |
211 ms |
391976 KB |
Output is correct |
3 |
Correct |
201 ms |
392008 KB |
Output is correct |
4 |
Correct |
203 ms |
391900 KB |
Output is correct |
5 |
Correct |
199 ms |
391944 KB |
Output is correct |
6 |
Correct |
191 ms |
391936 KB |
Output is correct |
7 |
Correct |
977 ms |
450532 KB |
Output is correct |
8 |
Correct |
2009 ms |
514928 KB |
Output is correct |
9 |
Correct |
2171 ms |
515540 KB |
Output is correct |
10 |
Correct |
1966 ms |
515396 KB |
Output is correct |
11 |
Correct |
403 ms |
416272 KB |
Output is correct |
12 |
Correct |
600 ms |
437992 KB |
Output is correct |
13 |
Correct |
620 ms |
441228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
392088 KB |
Output is correct |
2 |
Correct |
195 ms |
392012 KB |
Output is correct |
3 |
Correct |
190 ms |
392012 KB |
Output is correct |
4 |
Correct |
188 ms |
392004 KB |
Output is correct |
5 |
Correct |
192 ms |
392012 KB |
Output is correct |
6 |
Correct |
191 ms |
391916 KB |
Output is correct |
7 |
Correct |
195 ms |
391992 KB |
Output is correct |
8 |
Correct |
200 ms |
391980 KB |
Output is correct |
9 |
Correct |
194 ms |
391916 KB |
Output is correct |
10 |
Correct |
189 ms |
392128 KB |
Output is correct |
11 |
Correct |
196 ms |
392032 KB |
Output is correct |
12 |
Correct |
202 ms |
391924 KB |
Output is correct |
13 |
Correct |
193 ms |
391984 KB |
Output is correct |
14 |
Correct |
194 ms |
391908 KB |
Output is correct |
15 |
Correct |
203 ms |
392060 KB |
Output is correct |
16 |
Correct |
200 ms |
391892 KB |
Output is correct |
17 |
Correct |
192 ms |
392176 KB |
Output is correct |
18 |
Correct |
199 ms |
392180 KB |
Output is correct |
19 |
Correct |
218 ms |
392208 KB |
Output is correct |
20 |
Correct |
202 ms |
392080 KB |
Output is correct |
21 |
Correct |
223 ms |
392216 KB |
Output is correct |
22 |
Correct |
198 ms |
392392 KB |
Output is correct |
23 |
Correct |
202 ms |
392244 KB |
Output is correct |
24 |
Correct |
214 ms |
392012 KB |
Output is correct |
25 |
Correct |
233 ms |
393592 KB |
Output is correct |
26 |
Correct |
205 ms |
393548 KB |
Output is correct |
27 |
Correct |
222 ms |
393672 KB |
Output is correct |
28 |
Correct |
222 ms |
393368 KB |
Output is correct |
29 |
Correct |
221 ms |
393816 KB |
Output is correct |
30 |
Correct |
220 ms |
393844 KB |
Output is correct |
31 |
Correct |
236 ms |
393708 KB |
Output is correct |
32 |
Correct |
211 ms |
393788 KB |
Output is correct |
33 |
Correct |
308 ms |
413712 KB |
Output is correct |
34 |
Correct |
266 ms |
413632 KB |
Output is correct |
35 |
Correct |
270 ms |
413920 KB |
Output is correct |
36 |
Correct |
279 ms |
413676 KB |
Output is correct |
37 |
Correct |
386 ms |
408308 KB |
Output is correct |
38 |
Correct |
378 ms |
408304 KB |
Output is correct |
39 |
Correct |
395 ms |
408228 KB |
Output is correct |
40 |
Correct |
376 ms |
407880 KB |
Output is correct |
41 |
Correct |
309 ms |
402204 KB |
Output is correct |
42 |
Correct |
343 ms |
404980 KB |
Output is correct |
43 |
Correct |
435 ms |
408168 KB |
Output is correct |
44 |
Correct |
442 ms |
409124 KB |
Output is correct |
45 |
Correct |
312 ms |
401376 KB |
Output is correct |
46 |
Correct |
299 ms |
401452 KB |
Output is correct |
47 |
Correct |
438 ms |
408312 KB |
Output is correct |
48 |
Correct |
405 ms |
408364 KB |
Output is correct |
49 |
Correct |
201 ms |
392148 KB |
Output is correct |
50 |
Correct |
196 ms |
392084 KB |
Output is correct |
51 |
Correct |
203 ms |
392140 KB |
Output is correct |
52 |
Correct |
200 ms |
391980 KB |
Output is correct |
53 |
Correct |
198 ms |
392120 KB |
Output is correct |
54 |
Correct |
196 ms |
392028 KB |
Output is correct |
55 |
Correct |
205 ms |
392112 KB |
Output is correct |
56 |
Correct |
193 ms |
392012 KB |
Output is correct |
57 |
Correct |
192 ms |
392024 KB |
Output is correct |
58 |
Correct |
206 ms |
392016 KB |
Output is correct |
59 |
Correct |
192 ms |
391964 KB |
Output is correct |
60 |
Correct |
191 ms |
391936 KB |
Output is correct |
61 |
Correct |
977 ms |
450532 KB |
Output is correct |
62 |
Correct |
2009 ms |
514928 KB |
Output is correct |
63 |
Correct |
2171 ms |
515540 KB |
Output is correct |
64 |
Correct |
1966 ms |
515396 KB |
Output is correct |
65 |
Correct |
403 ms |
416272 KB |
Output is correct |
66 |
Correct |
600 ms |
437992 KB |
Output is correct |
67 |
Correct |
620 ms |
441228 KB |
Output is correct |
68 |
Correct |
207 ms |
391920 KB |
Output is correct |
69 |
Correct |
211 ms |
391976 KB |
Output is correct |
70 |
Correct |
201 ms |
392008 KB |
Output is correct |
71 |
Correct |
203 ms |
391900 KB |
Output is correct |
72 |
Correct |
199 ms |
391944 KB |
Output is correct |
73 |
Correct |
1738 ms |
636744 KB |
Output is correct |
74 |
Correct |
1498 ms |
636676 KB |
Output is correct |
75 |
Correct |
1459 ms |
636908 KB |
Output is correct |
76 |
Correct |
1244 ms |
636732 KB |
Output is correct |
77 |
Correct |
3206 ms |
581900 KB |
Output is correct |
78 |
Correct |
2471 ms |
514280 KB |
Output is correct |
79 |
Correct |
2834 ms |
531264 KB |
Output is correct |
80 |
Correct |
4287 ms |
603888 KB |
Output is correct |
81 |
Correct |
2514 ms |
530412 KB |
Output is correct |
82 |
Correct |
3690 ms |
599736 KB |
Output is correct |
83 |
Correct |
4392 ms |
630788 KB |
Output is correct |
84 |
Correct |
2200 ms |
518684 KB |
Output is correct |
85 |
Correct |
3918 ms |
626864 KB |
Output is correct |
86 |
Correct |
3748 ms |
622208 KB |
Output is correct |
87 |
Correct |
1976 ms |
525736 KB |
Output is correct |
88 |
Correct |
3247 ms |
629424 KB |
Output is correct |
89 |
Correct |
3256 ms |
629672 KB |
Output is correct |
90 |
Correct |
3218 ms |
629820 KB |
Output is correct |