#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = 2505;
vector<int> I[N][N], J[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
bool check(int i1, int j1, int i2, int j2){
if(i1 == -1 || j1 == -1 || i2 == -1 || j2 == -1) return false;
int il = lower_bound(I[j1][j2].begin(), I[j1][j2].end(), i1+1) - I[j1][j2].begin();
int ir = upper_bound(I[j1][j2].begin(), I[j1][j2].end(), i2-1) - I[j1][j2].begin();
ir -- ;
if(ir - il + 1 != (i2-1)-(i1+1)+1) return false;
il = lower_bound(J[i1][i2].begin(), J[i1][i2].end(), j1+1) - J[i1][i2].begin();
ir = upper_bound(J[i1][i2].begin(), J[i1][i2].end(), j2-1) - J[i1][i2].begin();
ir -- ;
if(ir - il + 1 != (j2-1)-(j1+1)+1) return false;
return true;
}
ll count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
for(int i = 0 ; i < n; i ++ ){
vector<int> st;
for(int j = 0 ; j < m ; j ++ ){
L[i][j] = -1;
while(!st.empty() && a[i][st.back()] <= a[i][j]) st.pop_back();
if(!st.empty()) L[i][j] = st.back();
st.push_back(j);
}
st.clear();
for(int j = 0 ; j < m ; j ++ ){
while(!st.empty() && a[i][st.back()] < a[i][j]) st.pop_back();
if(!st.empty()){
if(st.back() + 1 < j)I[st.back()][j].push_back(i);
}
st.push_back(j);
}
st.clear();
for(int j = m-1 ; j >= 0 ; j -- ){
R[i][j] = -1;
while(!st.empty() && a[i][st.back()] <= a[i][j]) st.pop_back();
if(!st.empty()) R[i][j] = st.back();
st.push_back(j);
}
st.clear();
for(int j = m - 1; j >= 0 ; j -- ){
while(!st.empty() && a[i][st.back()] < a[i][j]) st.pop_back();
if(!st.empty()){
if(j + 1 < st.back())I[j][st.back()].push_back(i);
}
st.push_back(j);
}
}
for(int j = 0 ; j < m ; j ++ ){
vector<int> st;
for(int i = 0 ; i < n; i ++ ){
U[i][j] = -1;
while(!st.empty() && a[st.back()][j] <= a[i][j]) st.pop_back();
if(!st.empty()) U[i][j] = st.back();
st.push_back(i);
}
st.clear();
for(int i = 0 ; i < n; i ++ ){
while(!st.empty() && a[st.back()][j] < a[i][j]) st.pop_back();
if(!st.empty()){
if(st.back() + 1 < i)
J[st.back()][i].push_back(j);
}
st.push_back(i);
}
st.clear();
for(int i = n - 1; i >= 0 ; i -- ){
D[i][j] = -1;
while(!st.empty() && a[st.back()][j] <= a[i][j]) st.pop_back();
if(!st.empty()) D[i][j] = st.back();
st.push_back(i);
}
st.clear();
for(int i = n - 1; i >= 0; i -- ){
while(!st.empty() && a[st.back()][j] < a[i][j]) st.pop_back();
if(!st.empty())
if(i + 1 < st.back())
J[i][st.back()].push_back(j);
st.push_back(i);
}
}
for(int i = 0; i < m; i ++ ){
for(int j = i + 1; j < m ; j ++ ){
sort(I[i][j].begin(), I[i][j].end());
I[i][j].resize(unique(I[i][j].begin(), I[i][j].end()) - I[i][j].begin());
}
}
for(int i = 0 ; i < n ; i ++ ){
for(int j = i + 1; j < n ; j ++ ){
sort(J[i][j].begin(), J[i][j].end());
J[i][j].resize(unique(J[i][j].begin(), J[i][j].end()) - J[i][j].begin());
}
}
vector<tuple<int,int,int,int>> sols;
for(int i = 1 ; i + 1 < n; i ++ ){
for(int j = 1; j + 1 < m ; j ++ ){
if(U[i][j] == -1 || L[i][j] == -1 || D[i][j] == -1 || R[i][j] == -1) continue;
if(check(U[i][j], L[i][j], D[i][j], R[i][j]))
sols.push_back({U[i][j], L[i][j], D[i][j], R[i][j]});
}
}
sort(sols.begin(), sols.end());
sols.resize(unique(sols.begin(), sols.end()) - sols.begin());
return sols.size();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
295160 KB |
Output is correct |
2 |
Correct |
224 ms |
295672 KB |
Output is correct |
3 |
Correct |
200 ms |
295544 KB |
Output is correct |
4 |
Correct |
200 ms |
295672 KB |
Output is correct |
5 |
Correct |
199 ms |
295544 KB |
Output is correct |
6 |
Correct |
212 ms |
295544 KB |
Output is correct |
7 |
Correct |
202 ms |
295672 KB |
Output is correct |
8 |
Correct |
203 ms |
295288 KB |
Output is correct |
9 |
Correct |
200 ms |
295544 KB |
Output is correct |
10 |
Correct |
198 ms |
295672 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295672 KB |
Output is correct |
13 |
Correct |
202 ms |
295160 KB |
Output is correct |
14 |
Correct |
204 ms |
295160 KB |
Output is correct |
15 |
Correct |
200 ms |
295160 KB |
Output is correct |
16 |
Correct |
203 ms |
295032 KB |
Output is correct |
17 |
Correct |
199 ms |
295160 KB |
Output is correct |
18 |
Correct |
204 ms |
295032 KB |
Output is correct |
19 |
Correct |
200 ms |
295544 KB |
Output is correct |
20 |
Correct |
199 ms |
295544 KB |
Output is correct |
21 |
Correct |
200 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
295160 KB |
Output is correct |
2 |
Correct |
224 ms |
295672 KB |
Output is correct |
3 |
Correct |
200 ms |
295544 KB |
Output is correct |
4 |
Correct |
200 ms |
295672 KB |
Output is correct |
5 |
Correct |
199 ms |
295544 KB |
Output is correct |
6 |
Correct |
212 ms |
295544 KB |
Output is correct |
7 |
Correct |
202 ms |
295672 KB |
Output is correct |
8 |
Correct |
203 ms |
295288 KB |
Output is correct |
9 |
Correct |
200 ms |
295544 KB |
Output is correct |
10 |
Correct |
198 ms |
295672 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295672 KB |
Output is correct |
13 |
Correct |
202 ms |
295160 KB |
Output is correct |
14 |
Correct |
204 ms |
295160 KB |
Output is correct |
15 |
Correct |
200 ms |
295160 KB |
Output is correct |
16 |
Correct |
203 ms |
295032 KB |
Output is correct |
17 |
Correct |
203 ms |
296816 KB |
Output is correct |
18 |
Correct |
202 ms |
296824 KB |
Output is correct |
19 |
Correct |
207 ms |
296844 KB |
Output is correct |
20 |
Correct |
206 ms |
296568 KB |
Output is correct |
21 |
Correct |
202 ms |
296696 KB |
Output is correct |
22 |
Correct |
210 ms |
296736 KB |
Output is correct |
23 |
Correct |
204 ms |
296696 KB |
Output is correct |
24 |
Correct |
199 ms |
296620 KB |
Output is correct |
25 |
Correct |
199 ms |
295160 KB |
Output is correct |
26 |
Correct |
204 ms |
295032 KB |
Output is correct |
27 |
Correct |
200 ms |
295544 KB |
Output is correct |
28 |
Correct |
199 ms |
295544 KB |
Output is correct |
29 |
Correct |
200 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
295160 KB |
Output is correct |
2 |
Correct |
224 ms |
295672 KB |
Output is correct |
3 |
Correct |
200 ms |
295544 KB |
Output is correct |
4 |
Correct |
200 ms |
295672 KB |
Output is correct |
5 |
Correct |
199 ms |
295544 KB |
Output is correct |
6 |
Correct |
212 ms |
295544 KB |
Output is correct |
7 |
Correct |
202 ms |
295672 KB |
Output is correct |
8 |
Correct |
203 ms |
295288 KB |
Output is correct |
9 |
Correct |
200 ms |
295544 KB |
Output is correct |
10 |
Correct |
198 ms |
295672 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295672 KB |
Output is correct |
13 |
Correct |
202 ms |
295160 KB |
Output is correct |
14 |
Correct |
204 ms |
295160 KB |
Output is correct |
15 |
Correct |
200 ms |
295160 KB |
Output is correct |
16 |
Correct |
203 ms |
295032 KB |
Output is correct |
17 |
Correct |
203 ms |
296816 KB |
Output is correct |
18 |
Correct |
202 ms |
296824 KB |
Output is correct |
19 |
Correct |
207 ms |
296844 KB |
Output is correct |
20 |
Correct |
206 ms |
296568 KB |
Output is correct |
21 |
Correct |
202 ms |
296696 KB |
Output is correct |
22 |
Correct |
210 ms |
296736 KB |
Output is correct |
23 |
Correct |
204 ms |
296696 KB |
Output is correct |
24 |
Correct |
199 ms |
296620 KB |
Output is correct |
25 |
Correct |
214 ms |
301084 KB |
Output is correct |
26 |
Correct |
215 ms |
301004 KB |
Output is correct |
27 |
Correct |
217 ms |
301044 KB |
Output is correct |
28 |
Correct |
211 ms |
299768 KB |
Output is correct |
29 |
Correct |
216 ms |
300408 KB |
Output is correct |
30 |
Correct |
234 ms |
300536 KB |
Output is correct |
31 |
Correct |
226 ms |
300644 KB |
Output is correct |
32 |
Correct |
217 ms |
300412 KB |
Output is correct |
33 |
Correct |
199 ms |
295160 KB |
Output is correct |
34 |
Correct |
204 ms |
295032 KB |
Output is correct |
35 |
Correct |
200 ms |
295544 KB |
Output is correct |
36 |
Correct |
199 ms |
295544 KB |
Output is correct |
37 |
Correct |
200 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
295160 KB |
Output is correct |
2 |
Correct |
224 ms |
295672 KB |
Output is correct |
3 |
Correct |
200 ms |
295544 KB |
Output is correct |
4 |
Correct |
200 ms |
295672 KB |
Output is correct |
5 |
Correct |
199 ms |
295544 KB |
Output is correct |
6 |
Correct |
212 ms |
295544 KB |
Output is correct |
7 |
Correct |
202 ms |
295672 KB |
Output is correct |
8 |
Correct |
203 ms |
295288 KB |
Output is correct |
9 |
Correct |
200 ms |
295544 KB |
Output is correct |
10 |
Correct |
198 ms |
295672 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295672 KB |
Output is correct |
13 |
Correct |
202 ms |
295160 KB |
Output is correct |
14 |
Correct |
204 ms |
295160 KB |
Output is correct |
15 |
Correct |
200 ms |
295160 KB |
Output is correct |
16 |
Correct |
203 ms |
295032 KB |
Output is correct |
17 |
Correct |
203 ms |
296816 KB |
Output is correct |
18 |
Correct |
202 ms |
296824 KB |
Output is correct |
19 |
Correct |
207 ms |
296844 KB |
Output is correct |
20 |
Correct |
206 ms |
296568 KB |
Output is correct |
21 |
Correct |
202 ms |
296696 KB |
Output is correct |
22 |
Correct |
210 ms |
296736 KB |
Output is correct |
23 |
Correct |
204 ms |
296696 KB |
Output is correct |
24 |
Correct |
199 ms |
296620 KB |
Output is correct |
25 |
Correct |
214 ms |
301084 KB |
Output is correct |
26 |
Correct |
215 ms |
301004 KB |
Output is correct |
27 |
Correct |
217 ms |
301044 KB |
Output is correct |
28 |
Correct |
211 ms |
299768 KB |
Output is correct |
29 |
Correct |
216 ms |
300408 KB |
Output is correct |
30 |
Correct |
234 ms |
300536 KB |
Output is correct |
31 |
Correct |
226 ms |
300644 KB |
Output is correct |
32 |
Correct |
217 ms |
300412 KB |
Output is correct |
33 |
Correct |
332 ms |
334584 KB |
Output is correct |
34 |
Correct |
314 ms |
334456 KB |
Output is correct |
35 |
Correct |
304 ms |
334584 KB |
Output is correct |
36 |
Correct |
297 ms |
334588 KB |
Output is correct |
37 |
Correct |
437 ms |
333236 KB |
Output is correct |
38 |
Correct |
422 ms |
333148 KB |
Output is correct |
39 |
Correct |
424 ms |
333280 KB |
Output is correct |
40 |
Correct |
427 ms |
331532 KB |
Output is correct |
41 |
Correct |
331 ms |
322196 KB |
Output is correct |
42 |
Correct |
373 ms |
323440 KB |
Output is correct |
43 |
Correct |
474 ms |
329724 KB |
Output is correct |
44 |
Correct |
467 ms |
330088 KB |
Output is correct |
45 |
Correct |
344 ms |
318960 KB |
Output is correct |
46 |
Correct |
324 ms |
313200 KB |
Output is correct |
47 |
Correct |
463 ms |
328804 KB |
Output is correct |
48 |
Correct |
466 ms |
328972 KB |
Output is correct |
49 |
Correct |
199 ms |
295160 KB |
Output is correct |
50 |
Correct |
204 ms |
295032 KB |
Output is correct |
51 |
Correct |
200 ms |
295544 KB |
Output is correct |
52 |
Correct |
199 ms |
295544 KB |
Output is correct |
53 |
Correct |
200 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
215 ms |
295544 KB |
Output is correct |
2 |
Correct |
209 ms |
295416 KB |
Output is correct |
3 |
Correct |
209 ms |
295288 KB |
Output is correct |
4 |
Correct |
203 ms |
295032 KB |
Output is correct |
5 |
Correct |
213 ms |
295544 KB |
Output is correct |
6 |
Correct |
211 ms |
295556 KB |
Output is correct |
7 |
Correct |
223 ms |
295676 KB |
Output is correct |
8 |
Correct |
216 ms |
295544 KB |
Output is correct |
9 |
Correct |
214 ms |
295544 KB |
Output is correct |
10 |
Correct |
215 ms |
295160 KB |
Output is correct |
11 |
Correct |
214 ms |
295288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
202 ms |
295160 KB |
Output is correct |
2 |
Correct |
1219 ms |
391200 KB |
Output is correct |
3 |
Correct |
2405 ms |
493000 KB |
Output is correct |
4 |
Correct |
2400 ms |
493760 KB |
Output is correct |
5 |
Correct |
2487 ms |
493980 KB |
Output is correct |
6 |
Correct |
546 ms |
369032 KB |
Output is correct |
7 |
Correct |
913 ms |
441304 KB |
Output is correct |
8 |
Correct |
984 ms |
444352 KB |
Output is correct |
9 |
Correct |
199 ms |
295160 KB |
Output is correct |
10 |
Correct |
204 ms |
295032 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
199 ms |
295544 KB |
Output is correct |
13 |
Correct |
200 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
295160 KB |
Output is correct |
2 |
Correct |
224 ms |
295672 KB |
Output is correct |
3 |
Correct |
200 ms |
295544 KB |
Output is correct |
4 |
Correct |
200 ms |
295672 KB |
Output is correct |
5 |
Correct |
199 ms |
295544 KB |
Output is correct |
6 |
Correct |
212 ms |
295544 KB |
Output is correct |
7 |
Correct |
202 ms |
295672 KB |
Output is correct |
8 |
Correct |
203 ms |
295288 KB |
Output is correct |
9 |
Correct |
200 ms |
295544 KB |
Output is correct |
10 |
Correct |
198 ms |
295672 KB |
Output is correct |
11 |
Correct |
200 ms |
295544 KB |
Output is correct |
12 |
Correct |
201 ms |
295672 KB |
Output is correct |
13 |
Correct |
202 ms |
295160 KB |
Output is correct |
14 |
Correct |
204 ms |
295160 KB |
Output is correct |
15 |
Correct |
200 ms |
295160 KB |
Output is correct |
16 |
Correct |
203 ms |
295032 KB |
Output is correct |
17 |
Correct |
203 ms |
296816 KB |
Output is correct |
18 |
Correct |
202 ms |
296824 KB |
Output is correct |
19 |
Correct |
207 ms |
296844 KB |
Output is correct |
20 |
Correct |
206 ms |
296568 KB |
Output is correct |
21 |
Correct |
202 ms |
296696 KB |
Output is correct |
22 |
Correct |
210 ms |
296736 KB |
Output is correct |
23 |
Correct |
204 ms |
296696 KB |
Output is correct |
24 |
Correct |
199 ms |
296620 KB |
Output is correct |
25 |
Correct |
214 ms |
301084 KB |
Output is correct |
26 |
Correct |
215 ms |
301004 KB |
Output is correct |
27 |
Correct |
217 ms |
301044 KB |
Output is correct |
28 |
Correct |
211 ms |
299768 KB |
Output is correct |
29 |
Correct |
216 ms |
300408 KB |
Output is correct |
30 |
Correct |
234 ms |
300536 KB |
Output is correct |
31 |
Correct |
226 ms |
300644 KB |
Output is correct |
32 |
Correct |
217 ms |
300412 KB |
Output is correct |
33 |
Correct |
332 ms |
334584 KB |
Output is correct |
34 |
Correct |
314 ms |
334456 KB |
Output is correct |
35 |
Correct |
304 ms |
334584 KB |
Output is correct |
36 |
Correct |
297 ms |
334588 KB |
Output is correct |
37 |
Correct |
437 ms |
333236 KB |
Output is correct |
38 |
Correct |
422 ms |
333148 KB |
Output is correct |
39 |
Correct |
424 ms |
333280 KB |
Output is correct |
40 |
Correct |
427 ms |
331532 KB |
Output is correct |
41 |
Correct |
331 ms |
322196 KB |
Output is correct |
42 |
Correct |
373 ms |
323440 KB |
Output is correct |
43 |
Correct |
474 ms |
329724 KB |
Output is correct |
44 |
Correct |
467 ms |
330088 KB |
Output is correct |
45 |
Correct |
344 ms |
318960 KB |
Output is correct |
46 |
Correct |
324 ms |
313200 KB |
Output is correct |
47 |
Correct |
463 ms |
328804 KB |
Output is correct |
48 |
Correct |
466 ms |
328972 KB |
Output is correct |
49 |
Correct |
215 ms |
295544 KB |
Output is correct |
50 |
Correct |
209 ms |
295416 KB |
Output is correct |
51 |
Correct |
209 ms |
295288 KB |
Output is correct |
52 |
Correct |
203 ms |
295032 KB |
Output is correct |
53 |
Correct |
213 ms |
295544 KB |
Output is correct |
54 |
Correct |
211 ms |
295556 KB |
Output is correct |
55 |
Correct |
223 ms |
295676 KB |
Output is correct |
56 |
Correct |
216 ms |
295544 KB |
Output is correct |
57 |
Correct |
214 ms |
295544 KB |
Output is correct |
58 |
Correct |
215 ms |
295160 KB |
Output is correct |
59 |
Correct |
214 ms |
295288 KB |
Output is correct |
60 |
Correct |
202 ms |
295160 KB |
Output is correct |
61 |
Correct |
1219 ms |
391200 KB |
Output is correct |
62 |
Correct |
2405 ms |
493000 KB |
Output is correct |
63 |
Correct |
2400 ms |
493760 KB |
Output is correct |
64 |
Correct |
2487 ms |
493980 KB |
Output is correct |
65 |
Correct |
546 ms |
369032 KB |
Output is correct |
66 |
Correct |
913 ms |
441304 KB |
Output is correct |
67 |
Correct |
984 ms |
444352 KB |
Output is correct |
68 |
Correct |
2052 ms |
639960 KB |
Output is correct |
69 |
Correct |
1748 ms |
638180 KB |
Output is correct |
70 |
Correct |
1898 ms |
638200 KB |
Output is correct |
71 |
Correct |
1670 ms |
637900 KB |
Output is correct |
72 |
Correct |
4253 ms |
648716 KB |
Output is correct |
73 |
Correct |
2879 ms |
463172 KB |
Output is correct |
74 |
Correct |
2952 ms |
510780 KB |
Output is correct |
75 |
Correct |
4987 ms |
583104 KB |
Output is correct |
76 |
Correct |
3002 ms |
465300 KB |
Output is correct |
77 |
Correct |
3810 ms |
530988 KB |
Output is correct |
78 |
Correct |
4939 ms |
585456 KB |
Output is correct |
79 |
Correct |
2955 ms |
472948 KB |
Output is correct |
80 |
Correct |
4996 ms |
587584 KB |
Output is correct |
81 |
Correct |
4800 ms |
581296 KB |
Output is correct |
82 |
Correct |
2361 ms |
537760 KB |
Output is correct |
83 |
Correct |
4277 ms |
660284 KB |
Output is correct |
84 |
Correct |
4112 ms |
660540 KB |
Output is correct |
85 |
Correct |
4445 ms |
660340 KB |
Output is correct |
86 |
Correct |
199 ms |
295160 KB |
Output is correct |
87 |
Correct |
204 ms |
295032 KB |
Output is correct |
88 |
Correct |
200 ms |
295544 KB |
Output is correct |
89 |
Correct |
199 ms |
295544 KB |
Output is correct |
90 |
Correct |
200 ms |
295244 KB |
Output is correct |