#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 2500
int n, m;
array<array<vector<int16_t>, MAXN>, MAXN> hors, verts;
vector<vector<signed>> aG;
void line(int i){
vector<int> records = {0};
for (int j = 1; j < m; ++j) {
bool rsame = false;
while (!records.empty() && aG[i][j] >= aG[i][records.back()]){
if (aG[i][j] == aG[i][records.back()]) rsame = true;
if (records.back() + 1 < j) hors[i][records.back() + 1].push_back(j - records.back() - 1);
records.pop_back();
}
if (!records.empty() && records.back() + 1 < j && !rsame) hors[i][records.back() + 1].push_back(j - records.back() - 1);
records.push_back(j);
}
}
void column(int j){
vector<int> records = {0};
for (int i = 1; i < n; ++i) {
bool rsame = false;
while (!records.empty() && aG[i][j] >= aG[records.back()][j]){
if (aG[i][j] == aG[records.back()][j]) rsame = true;
if (records.back() + 1 < i) verts[records.back() + 1][j].push_back(i - records.back() - 1);
records.pop_back();
}
if (!records.empty() && records.back() + 1 < i && !rsame) verts[records.back() + 1][j].push_back(i - records.back() - 1);
records.push_back(i);
}
}
long long count_rectangles(vector<vector<signed>> a){
n = a.size(); m = a[0].size(); swap(aG, a);
for (int i = 0; i < n; ++i) line(i);
for (int j = 0; j < m; ++j) column(j);
int ans = 0;
array<vector<pair<int, int>>, MAXN> lastr;
for (int j = m - 2; j >= 0; --j) {
array<vector<pair<int, int>>, MAXN> tr;
vector<pair<int, int>> down;
for (int i = n - 2; i >= 0; --i) {
sort(verts[i][j].begin(), verts[i][j].end());
auto itt = lastr[i].begin();
auto cs = verts[i][j].begin();
while (itt != lastr[i].end() && cs != verts[i][j].end()){
if ((*itt).second == *cs) tr[i].emplace_back((*itt++).first + 1, *cs++);
else if ((*itt).second < *cs) itt++;
else tr[i].emplace_back(1, *cs++);;
}
while (cs != verts[i][j].end()) tr[i].emplace_back(1, *cs++);
vector<pair<int, int>> here;
sort(hors[i][j].begin(), hors[i][j].end());
itt = down.begin();
cs = hors[i][j].begin();
while (itt != down.end() && cs != hors[i][j].end()){
if ((*itt).first == *cs) here.emplace_back(*cs++, (*itt++).second + 1);
else if ((*itt).first < *cs) itt++;
else here.emplace_back(*cs++, 1);
}
while (cs != hors[i][j].end()) here.emplace_back(*cs++, 1);
multiset<int> hlimits;
vector<pair<int, int>> vcopy = tr[i];
sort(vcopy.begin(), vcopy.end());
auto hor = here.begin();
auto ver = vcopy.begin();
while (hor != here.end() && ver != vcopy.end()){
if ((*hor).first <= (*ver).first) hlimits.insert((*hor++).second);
else ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
}
while (ver != vcopy.end()) ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
swap(down, here);
}
swap(lastr, tr);
}
return ans;
}
/*
signed main(){
cerr << count_rectangles({{10, 9, 8, 9, 10},
{9 , 8, 7, 8, 9 },
{8 , 7, 6, 7, 8 },
{7 , 6, 5, 6, 7 },
{8 , 7, 6, 7, 8 },
{9 , 8, 7, 8, 9 },
{10, 9, 8, 9, 10}}) << "\n";
return 0;
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
293836 KB |
Output is correct |
2 |
Correct |
120 ms |
293952 KB |
Output is correct |
3 |
Correct |
121 ms |
293984 KB |
Output is correct |
4 |
Correct |
131 ms |
293972 KB |
Output is correct |
5 |
Correct |
122 ms |
293940 KB |
Output is correct |
6 |
Correct |
122 ms |
293904 KB |
Output is correct |
7 |
Correct |
136 ms |
293888 KB |
Output is correct |
8 |
Correct |
126 ms |
293900 KB |
Output is correct |
9 |
Correct |
126 ms |
293960 KB |
Output is correct |
10 |
Correct |
142 ms |
293964 KB |
Output is correct |
11 |
Correct |
124 ms |
293968 KB |
Output is correct |
12 |
Correct |
124 ms |
293936 KB |
Output is correct |
13 |
Correct |
121 ms |
293852 KB |
Output is correct |
14 |
Correct |
122 ms |
293848 KB |
Output is correct |
15 |
Correct |
125 ms |
293880 KB |
Output is correct |
16 |
Correct |
121 ms |
293864 KB |
Output is correct |
17 |
Correct |
123 ms |
293920 KB |
Output is correct |
18 |
Correct |
138 ms |
293900 KB |
Output is correct |
19 |
Correct |
121 ms |
293916 KB |
Output is correct |
20 |
Correct |
124 ms |
293820 KB |
Output is correct |
21 |
Correct |
126 ms |
293908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
293836 KB |
Output is correct |
2 |
Correct |
120 ms |
293952 KB |
Output is correct |
3 |
Correct |
121 ms |
293984 KB |
Output is correct |
4 |
Correct |
131 ms |
293972 KB |
Output is correct |
5 |
Correct |
122 ms |
293940 KB |
Output is correct |
6 |
Correct |
122 ms |
293904 KB |
Output is correct |
7 |
Correct |
136 ms |
293888 KB |
Output is correct |
8 |
Correct |
126 ms |
293900 KB |
Output is correct |
9 |
Correct |
126 ms |
293960 KB |
Output is correct |
10 |
Correct |
142 ms |
293964 KB |
Output is correct |
11 |
Correct |
124 ms |
293968 KB |
Output is correct |
12 |
Correct |
124 ms |
293936 KB |
Output is correct |
13 |
Correct |
121 ms |
293852 KB |
Output is correct |
14 |
Correct |
122 ms |
293848 KB |
Output is correct |
15 |
Correct |
125 ms |
293880 KB |
Output is correct |
16 |
Correct |
121 ms |
293864 KB |
Output is correct |
17 |
Correct |
123 ms |
293920 KB |
Output is correct |
18 |
Correct |
138 ms |
293900 KB |
Output is correct |
19 |
Correct |
121 ms |
293916 KB |
Output is correct |
20 |
Correct |
124 ms |
293820 KB |
Output is correct |
21 |
Correct |
126 ms |
293908 KB |
Output is correct |
22 |
Correct |
128 ms |
294356 KB |
Output is correct |
23 |
Correct |
133 ms |
294268 KB |
Output is correct |
24 |
Correct |
123 ms |
294376 KB |
Output is correct |
25 |
Correct |
123 ms |
294116 KB |
Output is correct |
26 |
Correct |
144 ms |
294172 KB |
Output is correct |
27 |
Correct |
125 ms |
294092 KB |
Output is correct |
28 |
Correct |
141 ms |
294056 KB |
Output is correct |
29 |
Correct |
122 ms |
294028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
293836 KB |
Output is correct |
2 |
Correct |
120 ms |
293952 KB |
Output is correct |
3 |
Correct |
121 ms |
293984 KB |
Output is correct |
4 |
Correct |
131 ms |
293972 KB |
Output is correct |
5 |
Correct |
122 ms |
293940 KB |
Output is correct |
6 |
Correct |
122 ms |
293904 KB |
Output is correct |
7 |
Correct |
136 ms |
293888 KB |
Output is correct |
8 |
Correct |
126 ms |
293900 KB |
Output is correct |
9 |
Correct |
126 ms |
293960 KB |
Output is correct |
10 |
Correct |
142 ms |
293964 KB |
Output is correct |
11 |
Correct |
124 ms |
293968 KB |
Output is correct |
12 |
Correct |
124 ms |
293936 KB |
Output is correct |
13 |
Correct |
121 ms |
293852 KB |
Output is correct |
14 |
Correct |
122 ms |
293848 KB |
Output is correct |
15 |
Correct |
125 ms |
293880 KB |
Output is correct |
16 |
Correct |
121 ms |
293864 KB |
Output is correct |
17 |
Correct |
128 ms |
294356 KB |
Output is correct |
18 |
Correct |
133 ms |
294268 KB |
Output is correct |
19 |
Correct |
123 ms |
294376 KB |
Output is correct |
20 |
Correct |
123 ms |
294116 KB |
Output is correct |
21 |
Correct |
144 ms |
294172 KB |
Output is correct |
22 |
Correct |
125 ms |
294092 KB |
Output is correct |
23 |
Correct |
141 ms |
294056 KB |
Output is correct |
24 |
Correct |
122 ms |
294028 KB |
Output is correct |
25 |
Correct |
123 ms |
293920 KB |
Output is correct |
26 |
Correct |
138 ms |
293900 KB |
Output is correct |
27 |
Correct |
121 ms |
293916 KB |
Output is correct |
28 |
Correct |
124 ms |
293820 KB |
Output is correct |
29 |
Correct |
126 ms |
293908 KB |
Output is correct |
30 |
Correct |
133 ms |
296736 KB |
Output is correct |
31 |
Correct |
132 ms |
296740 KB |
Output is correct |
32 |
Correct |
133 ms |
296620 KB |
Output is correct |
33 |
Correct |
129 ms |
294988 KB |
Output is correct |
34 |
Correct |
134 ms |
295496 KB |
Output is correct |
35 |
Correct |
135 ms |
295396 KB |
Output is correct |
36 |
Correct |
139 ms |
295320 KB |
Output is correct |
37 |
Correct |
136 ms |
295352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
293836 KB |
Output is correct |
2 |
Correct |
120 ms |
293952 KB |
Output is correct |
3 |
Correct |
121 ms |
293984 KB |
Output is correct |
4 |
Correct |
131 ms |
293972 KB |
Output is correct |
5 |
Correct |
122 ms |
293940 KB |
Output is correct |
6 |
Correct |
122 ms |
293904 KB |
Output is correct |
7 |
Correct |
136 ms |
293888 KB |
Output is correct |
8 |
Correct |
126 ms |
293900 KB |
Output is correct |
9 |
Correct |
126 ms |
293960 KB |
Output is correct |
10 |
Correct |
142 ms |
293964 KB |
Output is correct |
11 |
Correct |
124 ms |
293968 KB |
Output is correct |
12 |
Correct |
124 ms |
293936 KB |
Output is correct |
13 |
Correct |
121 ms |
293852 KB |
Output is correct |
14 |
Correct |
122 ms |
293848 KB |
Output is correct |
15 |
Correct |
125 ms |
293880 KB |
Output is correct |
16 |
Correct |
121 ms |
293864 KB |
Output is correct |
17 |
Correct |
128 ms |
294356 KB |
Output is correct |
18 |
Correct |
133 ms |
294268 KB |
Output is correct |
19 |
Correct |
123 ms |
294376 KB |
Output is correct |
20 |
Correct |
123 ms |
294116 KB |
Output is correct |
21 |
Correct |
144 ms |
294172 KB |
Output is correct |
22 |
Correct |
125 ms |
294092 KB |
Output is correct |
23 |
Correct |
141 ms |
294056 KB |
Output is correct |
24 |
Correct |
122 ms |
294028 KB |
Output is correct |
25 |
Correct |
133 ms |
296736 KB |
Output is correct |
26 |
Correct |
132 ms |
296740 KB |
Output is correct |
27 |
Correct |
133 ms |
296620 KB |
Output is correct |
28 |
Correct |
129 ms |
294988 KB |
Output is correct |
29 |
Correct |
134 ms |
295496 KB |
Output is correct |
30 |
Correct |
135 ms |
295396 KB |
Output is correct |
31 |
Correct |
139 ms |
295320 KB |
Output is correct |
32 |
Correct |
136 ms |
295352 KB |
Output is correct |
33 |
Correct |
123 ms |
293920 KB |
Output is correct |
34 |
Correct |
138 ms |
293900 KB |
Output is correct |
35 |
Correct |
121 ms |
293916 KB |
Output is correct |
36 |
Correct |
124 ms |
293820 KB |
Output is correct |
37 |
Correct |
126 ms |
293908 KB |
Output is correct |
38 |
Correct |
221 ms |
313048 KB |
Output is correct |
39 |
Correct |
194 ms |
306236 KB |
Output is correct |
40 |
Correct |
197 ms |
306224 KB |
Output is correct |
41 |
Correct |
164 ms |
299340 KB |
Output is correct |
42 |
Correct |
311 ms |
328440 KB |
Output is correct |
43 |
Correct |
290 ms |
328400 KB |
Output is correct |
44 |
Correct |
292 ms |
328444 KB |
Output is correct |
45 |
Correct |
265 ms |
326092 KB |
Output is correct |
46 |
Correct |
201 ms |
305548 KB |
Output is correct |
47 |
Correct |
222 ms |
308024 KB |
Output is correct |
48 |
Correct |
286 ms |
313096 KB |
Output is correct |
49 |
Correct |
293 ms |
313068 KB |
Output is correct |
50 |
Correct |
209 ms |
303456 KB |
Output is correct |
51 |
Correct |
226 ms |
303436 KB |
Output is correct |
52 |
Correct |
279 ms |
311812 KB |
Output is correct |
53 |
Correct |
286 ms |
312140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
145 ms |
294196 KB |
Output is correct |
2 |
Correct |
145 ms |
294188 KB |
Output is correct |
3 |
Correct |
144 ms |
294000 KB |
Output is correct |
4 |
Correct |
123 ms |
293944 KB |
Output is correct |
5 |
Correct |
144 ms |
294132 KB |
Output is correct |
6 |
Correct |
149 ms |
294136 KB |
Output is correct |
7 |
Correct |
144 ms |
294136 KB |
Output is correct |
8 |
Correct |
151 ms |
294068 KB |
Output is correct |
9 |
Correct |
142 ms |
294004 KB |
Output is correct |
10 |
Correct |
164 ms |
293996 KB |
Output is correct |
11 |
Correct |
176 ms |
294020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
293920 KB |
Output is correct |
2 |
Correct |
138 ms |
293900 KB |
Output is correct |
3 |
Correct |
121 ms |
293916 KB |
Output is correct |
4 |
Correct |
124 ms |
293820 KB |
Output is correct |
5 |
Correct |
126 ms |
293908 KB |
Output is correct |
6 |
Correct |
153 ms |
293860 KB |
Output is correct |
7 |
Correct |
867 ms |
361172 KB |
Output is correct |
8 |
Correct |
1321 ms |
440008 KB |
Output is correct |
9 |
Correct |
1431 ms |
440720 KB |
Output is correct |
10 |
Correct |
1310 ms |
440772 KB |
Output is correct |
11 |
Correct |
432 ms |
318176 KB |
Output is correct |
12 |
Correct |
724 ms |
340004 KB |
Output is correct |
13 |
Correct |
743 ms |
343048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
293836 KB |
Output is correct |
2 |
Correct |
120 ms |
293952 KB |
Output is correct |
3 |
Correct |
121 ms |
293984 KB |
Output is correct |
4 |
Correct |
131 ms |
293972 KB |
Output is correct |
5 |
Correct |
122 ms |
293940 KB |
Output is correct |
6 |
Correct |
122 ms |
293904 KB |
Output is correct |
7 |
Correct |
136 ms |
293888 KB |
Output is correct |
8 |
Correct |
126 ms |
293900 KB |
Output is correct |
9 |
Correct |
126 ms |
293960 KB |
Output is correct |
10 |
Correct |
142 ms |
293964 KB |
Output is correct |
11 |
Correct |
124 ms |
293968 KB |
Output is correct |
12 |
Correct |
124 ms |
293936 KB |
Output is correct |
13 |
Correct |
121 ms |
293852 KB |
Output is correct |
14 |
Correct |
122 ms |
293848 KB |
Output is correct |
15 |
Correct |
125 ms |
293880 KB |
Output is correct |
16 |
Correct |
121 ms |
293864 KB |
Output is correct |
17 |
Correct |
128 ms |
294356 KB |
Output is correct |
18 |
Correct |
133 ms |
294268 KB |
Output is correct |
19 |
Correct |
123 ms |
294376 KB |
Output is correct |
20 |
Correct |
123 ms |
294116 KB |
Output is correct |
21 |
Correct |
144 ms |
294172 KB |
Output is correct |
22 |
Correct |
125 ms |
294092 KB |
Output is correct |
23 |
Correct |
141 ms |
294056 KB |
Output is correct |
24 |
Correct |
122 ms |
294028 KB |
Output is correct |
25 |
Correct |
133 ms |
296736 KB |
Output is correct |
26 |
Correct |
132 ms |
296740 KB |
Output is correct |
27 |
Correct |
133 ms |
296620 KB |
Output is correct |
28 |
Correct |
129 ms |
294988 KB |
Output is correct |
29 |
Correct |
134 ms |
295496 KB |
Output is correct |
30 |
Correct |
135 ms |
295396 KB |
Output is correct |
31 |
Correct |
139 ms |
295320 KB |
Output is correct |
32 |
Correct |
136 ms |
295352 KB |
Output is correct |
33 |
Correct |
221 ms |
313048 KB |
Output is correct |
34 |
Correct |
194 ms |
306236 KB |
Output is correct |
35 |
Correct |
197 ms |
306224 KB |
Output is correct |
36 |
Correct |
164 ms |
299340 KB |
Output is correct |
37 |
Correct |
311 ms |
328440 KB |
Output is correct |
38 |
Correct |
290 ms |
328400 KB |
Output is correct |
39 |
Correct |
292 ms |
328444 KB |
Output is correct |
40 |
Correct |
265 ms |
326092 KB |
Output is correct |
41 |
Correct |
201 ms |
305548 KB |
Output is correct |
42 |
Correct |
222 ms |
308024 KB |
Output is correct |
43 |
Correct |
286 ms |
313096 KB |
Output is correct |
44 |
Correct |
293 ms |
313068 KB |
Output is correct |
45 |
Correct |
209 ms |
303456 KB |
Output is correct |
46 |
Correct |
226 ms |
303436 KB |
Output is correct |
47 |
Correct |
279 ms |
311812 KB |
Output is correct |
48 |
Correct |
286 ms |
312140 KB |
Output is correct |
49 |
Correct |
145 ms |
294196 KB |
Output is correct |
50 |
Correct |
145 ms |
294188 KB |
Output is correct |
51 |
Correct |
144 ms |
294000 KB |
Output is correct |
52 |
Correct |
123 ms |
293944 KB |
Output is correct |
53 |
Correct |
144 ms |
294132 KB |
Output is correct |
54 |
Correct |
149 ms |
294136 KB |
Output is correct |
55 |
Correct |
144 ms |
294136 KB |
Output is correct |
56 |
Correct |
151 ms |
294068 KB |
Output is correct |
57 |
Correct |
142 ms |
294004 KB |
Output is correct |
58 |
Correct |
164 ms |
293996 KB |
Output is correct |
59 |
Correct |
176 ms |
294020 KB |
Output is correct |
60 |
Correct |
153 ms |
293860 KB |
Output is correct |
61 |
Correct |
867 ms |
361172 KB |
Output is correct |
62 |
Correct |
1321 ms |
440008 KB |
Output is correct |
63 |
Correct |
1431 ms |
440720 KB |
Output is correct |
64 |
Correct |
1310 ms |
440772 KB |
Output is correct |
65 |
Correct |
432 ms |
318176 KB |
Output is correct |
66 |
Correct |
724 ms |
340004 KB |
Output is correct |
67 |
Correct |
743 ms |
343048 KB |
Output is correct |
68 |
Correct |
123 ms |
293920 KB |
Output is correct |
69 |
Correct |
138 ms |
293900 KB |
Output is correct |
70 |
Correct |
121 ms |
293916 KB |
Output is correct |
71 |
Correct |
124 ms |
293820 KB |
Output is correct |
72 |
Correct |
126 ms |
293908 KB |
Output is correct |
73 |
Correct |
1927 ms |
538744 KB |
Output is correct |
74 |
Correct |
1789 ms |
450148 KB |
Output is correct |
75 |
Correct |
1235 ms |
450020 KB |
Output is correct |
76 |
Correct |
997 ms |
361360 KB |
Output is correct |
77 |
Correct |
2708 ms |
782008 KB |
Output is correct |
78 |
Correct |
1485 ms |
454156 KB |
Output is correct |
79 |
Correct |
1959 ms |
470592 KB |
Output is correct |
80 |
Correct |
2876 ms |
561076 KB |
Output is correct |
81 |
Correct |
1678 ms |
469500 KB |
Output is correct |
82 |
Correct |
2188 ms |
528240 KB |
Output is correct |
83 |
Correct |
2713 ms |
586788 KB |
Output is correct |
84 |
Correct |
1503 ms |
453316 KB |
Output is correct |
85 |
Correct |
2592 ms |
573288 KB |
Output is correct |
86 |
Correct |
2673 ms |
564852 KB |
Output is correct |
87 |
Correct |
1768 ms |
586844 KB |
Output is correct |
88 |
Correct |
2647 ms |
781672 KB |
Output is correct |
89 |
Correct |
2478 ms |
782000 KB |
Output is correct |
90 |
Correct |
2624 ms |
782076 KB |
Output is correct |