#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=2510;
int N, M, A[Nmax][Nmax], L[Nmax][Nmax], R[Nmax][Nmax], D[Nmax][Nmax], U[Nmax][Nmax];
vector<tuple<int, int, int, int>> X, Y;
ll count_rectangles(vector<vector<int> > a) {
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++) {
stack<pair<int, int>> S;
for(int j=1; j<=M; j++) {
while(!S.empty() && S.top().first<=A[i][j]) S.pop();
if(!S.empty()) L[i][j]=S.top().second;
S.push({A[i][j], j});
}
while(!S.empty()) S.pop();
for(int j=M; j>=1; j--) {
while(!S.empty() && S.top().first<=A[i][j]) S.pop();
if(!S.empty()) R[i][j]=S.top().second;
S.push({A[i][j], j});
}
}
for(int j=1; j<=M; j++) {
stack<pair<int, int>> S;
for(int i=1; i<=N; i++) {
while(!S.empty() && S.top().first<=A[i][j]) S.pop();
if(!S.empty()) U[i][j]=S.top().second;
S.push({A[i][j], i});
}
while(!S.empty()) S.pop();
for(int i=N; i>=1; i--) {
while(!S.empty() && S.top().first<=A[i][j]) S.pop();
if(!S.empty()) D[i][j]=S.top().second;
S.push({A[i][j], i});
}
}
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
if(L[i][j] && R[i][j]) X.push_back({L[i][j]+1, R[i][j]-1, i, i});
if(U[i][j] && D[i][j]) Y.push_back({U[i][j]+1, D[i][j]-1, j, j});
}
sort(X.begin(), X.end()), sort(Y.begin(), Y.end());
X.erase(unique(X.begin(), X.end()), X.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
for(int i=(int)X.size()-2; i>=0; i--) {
auto [l, r, y, v]=X[i];
auto [ll, rr, yy, vv]=X[i+1];
if(l==ll && r==rr && y+1==yy) X[i]={l, r, y, vv};
}
for(int i=(int)Y.size()-2; i>=0; i--) {
auto [l, r, x, v]=Y[i];
auto [ll, rr, xx, vv]=Y[i+1];
if(l==ll && r==rr && x+1==xx) Y[i]={l, r, x, vv};
}
vector<ll> ret;
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
if(!L[i][j] || !R[i][j] || !U[i][j] || !D[i][j]) continue;
auto p=lower_bound(X.begin(), X.end(), make_tuple(L[i][j]+1, R[i][j]-1, U[i][j]+1, 0));
if(p==X.end()) continue;
auto [l, r, y, v]=(*p);
if(l!=L[i][j]+1 || r!=R[i][j]-1 || y!=U[i][j]+1 || v<D[i][j]-1) continue;
auto q=lower_bound(Y.begin(), Y.end(), make_tuple(U[i][j]+1, D[i][j]-1, L[i][j]+1, 0));
if(q==Y.end()) continue;
auto [ll, rr, xx, vv]=(*q);
if(ll!=U[i][j]+1 || rr!=D[i][j]-1 || xx!=L[i][j]+1 || vv<R[i][j]-1) continue;
ret.push_back(L[i][j]*2500ll*2500ll*2500ll+R[i][j]*2500ll*2500ll+U[i][j]*2500ll+D[i][j]);
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret.size();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
3 ms |
19024 KB |
Output is correct |
3 |
Correct |
3 ms |
19036 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
19036 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
3 ms |
19036 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
0 ms |
2392 KB |
Output is correct |
14 |
Correct |
2 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
8632 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
3 ms |
18780 KB |
Output is correct |
20 |
Correct |
2 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
4696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
3 ms |
19024 KB |
Output is correct |
3 |
Correct |
3 ms |
19036 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
19036 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
3 ms |
19036 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
0 ms |
2392 KB |
Output is correct |
14 |
Correct |
2 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
8632 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
3 ms |
18780 KB |
Output is correct |
20 |
Correct |
2 ms |
12636 KB |
Output is correct |
21 |
Correct |
1 ms |
4696 KB |
Output is correct |
22 |
Correct |
5 ms |
19292 KB |
Output is correct |
23 |
Correct |
5 ms |
19288 KB |
Output is correct |
24 |
Correct |
5 ms |
19488 KB |
Output is correct |
25 |
Correct |
4 ms |
19036 KB |
Output is correct |
26 |
Correct |
5 ms |
19292 KB |
Output is correct |
27 |
Correct |
6 ms |
19288 KB |
Output is correct |
28 |
Correct |
5 ms |
19292 KB |
Output is correct |
29 |
Correct |
4 ms |
19036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
3 ms |
19024 KB |
Output is correct |
3 |
Correct |
3 ms |
19036 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
19036 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
3 ms |
19036 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
0 ms |
2392 KB |
Output is correct |
14 |
Correct |
2 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
8632 KB |
Output is correct |
17 |
Correct |
5 ms |
19292 KB |
Output is correct |
18 |
Correct |
5 ms |
19288 KB |
Output is correct |
19 |
Correct |
5 ms |
19488 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
5 ms |
19292 KB |
Output is correct |
22 |
Correct |
6 ms |
19288 KB |
Output is correct |
23 |
Correct |
5 ms |
19292 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
1 ms |
2396 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
3 ms |
18780 KB |
Output is correct |
28 |
Correct |
2 ms |
12636 KB |
Output is correct |
29 |
Correct |
1 ms |
4696 KB |
Output is correct |
30 |
Correct |
19 ms |
21404 KB |
Output is correct |
31 |
Correct |
19 ms |
21504 KB |
Output is correct |
32 |
Correct |
19 ms |
21444 KB |
Output is correct |
33 |
Correct |
15 ms |
20436 KB |
Output is correct |
34 |
Correct |
20 ms |
21028 KB |
Output is correct |
35 |
Correct |
21 ms |
21280 KB |
Output is correct |
36 |
Correct |
23 ms |
21024 KB |
Output is correct |
37 |
Correct |
20 ms |
21284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
3 ms |
19024 KB |
Output is correct |
3 |
Correct |
3 ms |
19036 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
19036 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
3 ms |
19036 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
0 ms |
2392 KB |
Output is correct |
14 |
Correct |
2 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
8632 KB |
Output is correct |
17 |
Correct |
5 ms |
19292 KB |
Output is correct |
18 |
Correct |
5 ms |
19288 KB |
Output is correct |
19 |
Correct |
5 ms |
19488 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
5 ms |
19292 KB |
Output is correct |
22 |
Correct |
6 ms |
19288 KB |
Output is correct |
23 |
Correct |
5 ms |
19292 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
19 ms |
21404 KB |
Output is correct |
26 |
Correct |
19 ms |
21504 KB |
Output is correct |
27 |
Correct |
19 ms |
21444 KB |
Output is correct |
28 |
Correct |
15 ms |
20436 KB |
Output is correct |
29 |
Correct |
20 ms |
21028 KB |
Output is correct |
30 |
Correct |
21 ms |
21280 KB |
Output is correct |
31 |
Correct |
23 ms |
21024 KB |
Output is correct |
32 |
Correct |
20 ms |
21284 KB |
Output is correct |
33 |
Correct |
1 ms |
2396 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Correct |
3 ms |
18780 KB |
Output is correct |
36 |
Correct |
2 ms |
12636 KB |
Output is correct |
37 |
Correct |
1 ms |
4696 KB |
Output is correct |
38 |
Correct |
78 ms |
65492 KB |
Output is correct |
39 |
Correct |
69 ms |
66236 KB |
Output is correct |
40 |
Correct |
84 ms |
66924 KB |
Output is correct |
41 |
Correct |
70 ms |
66236 KB |
Output is correct |
42 |
Correct |
241 ms |
78484 KB |
Output is correct |
43 |
Correct |
237 ms |
78860 KB |
Output is correct |
44 |
Correct |
238 ms |
78984 KB |
Output is correct |
45 |
Correct |
230 ms |
79760 KB |
Output is correct |
46 |
Correct |
125 ms |
64176 KB |
Output is correct |
47 |
Correct |
165 ms |
69368 KB |
Output is correct |
48 |
Correct |
265 ms |
73964 KB |
Output is correct |
49 |
Correct |
256 ms |
73928 KB |
Output is correct |
50 |
Correct |
129 ms |
62152 KB |
Output is correct |
51 |
Correct |
127 ms |
41620 KB |
Output is correct |
52 |
Correct |
260 ms |
75372 KB |
Output is correct |
53 |
Correct |
260 ms |
74672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11096 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
11096 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
3 ms |
11100 KB |
Output is correct |
8 |
Correct |
3 ms |
10844 KB |
Output is correct |
9 |
Correct |
3 ms |
11100 KB |
Output is correct |
10 |
Correct |
1 ms |
6620 KB |
Output is correct |
11 |
Correct |
2 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
12636 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
2 ms |
12636 KB |
Output is correct |
7 |
Correct |
753 ms |
148812 KB |
Output is correct |
8 |
Correct |
1768 ms |
282684 KB |
Output is correct |
9 |
Correct |
1784 ms |
283424 KB |
Output is correct |
10 |
Correct |
1766 ms |
283440 KB |
Output is correct |
11 |
Correct |
165 ms |
58792 KB |
Output is correct |
12 |
Correct |
305 ms |
105808 KB |
Output is correct |
13 |
Correct |
332 ms |
109280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
3 ms |
19024 KB |
Output is correct |
3 |
Correct |
3 ms |
19036 KB |
Output is correct |
4 |
Correct |
3 ms |
19036 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
19036 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
2 ms |
14684 KB |
Output is correct |
9 |
Correct |
3 ms |
19036 KB |
Output is correct |
10 |
Correct |
3 ms |
18776 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18780 KB |
Output is correct |
13 |
Correct |
0 ms |
2392 KB |
Output is correct |
14 |
Correct |
2 ms |
12636 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
8632 KB |
Output is correct |
17 |
Correct |
5 ms |
19292 KB |
Output is correct |
18 |
Correct |
5 ms |
19288 KB |
Output is correct |
19 |
Correct |
5 ms |
19488 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
5 ms |
19292 KB |
Output is correct |
22 |
Correct |
6 ms |
19288 KB |
Output is correct |
23 |
Correct |
5 ms |
19292 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
19 ms |
21404 KB |
Output is correct |
26 |
Correct |
19 ms |
21504 KB |
Output is correct |
27 |
Correct |
19 ms |
21444 KB |
Output is correct |
28 |
Correct |
15 ms |
20436 KB |
Output is correct |
29 |
Correct |
20 ms |
21028 KB |
Output is correct |
30 |
Correct |
21 ms |
21280 KB |
Output is correct |
31 |
Correct |
23 ms |
21024 KB |
Output is correct |
32 |
Correct |
20 ms |
21284 KB |
Output is correct |
33 |
Correct |
78 ms |
65492 KB |
Output is correct |
34 |
Correct |
69 ms |
66236 KB |
Output is correct |
35 |
Correct |
84 ms |
66924 KB |
Output is correct |
36 |
Correct |
70 ms |
66236 KB |
Output is correct |
37 |
Correct |
241 ms |
78484 KB |
Output is correct |
38 |
Correct |
237 ms |
78860 KB |
Output is correct |
39 |
Correct |
238 ms |
78984 KB |
Output is correct |
40 |
Correct |
230 ms |
79760 KB |
Output is correct |
41 |
Correct |
125 ms |
64176 KB |
Output is correct |
42 |
Correct |
165 ms |
69368 KB |
Output is correct |
43 |
Correct |
265 ms |
73964 KB |
Output is correct |
44 |
Correct |
256 ms |
73928 KB |
Output is correct |
45 |
Correct |
129 ms |
62152 KB |
Output is correct |
46 |
Correct |
127 ms |
41620 KB |
Output is correct |
47 |
Correct |
260 ms |
75372 KB |
Output is correct |
48 |
Correct |
260 ms |
74672 KB |
Output is correct |
49 |
Correct |
3 ms |
11096 KB |
Output is correct |
50 |
Correct |
2 ms |
10844 KB |
Output is correct |
51 |
Correct |
1 ms |
4444 KB |
Output is correct |
52 |
Correct |
1 ms |
4444 KB |
Output is correct |
53 |
Correct |
3 ms |
11096 KB |
Output is correct |
54 |
Correct |
3 ms |
11100 KB |
Output is correct |
55 |
Correct |
3 ms |
11100 KB |
Output is correct |
56 |
Correct |
3 ms |
10844 KB |
Output is correct |
57 |
Correct |
3 ms |
11100 KB |
Output is correct |
58 |
Correct |
1 ms |
6620 KB |
Output is correct |
59 |
Correct |
2 ms |
8796 KB |
Output is correct |
60 |
Correct |
2 ms |
12636 KB |
Output is correct |
61 |
Correct |
753 ms |
148812 KB |
Output is correct |
62 |
Correct |
1768 ms |
282684 KB |
Output is correct |
63 |
Correct |
1784 ms |
283424 KB |
Output is correct |
64 |
Correct |
1766 ms |
283440 KB |
Output is correct |
65 |
Correct |
165 ms |
58792 KB |
Output is correct |
66 |
Correct |
305 ms |
105808 KB |
Output is correct |
67 |
Correct |
332 ms |
109280 KB |
Output is correct |
68 |
Correct |
1 ms |
2396 KB |
Output is correct |
69 |
Correct |
1 ms |
6492 KB |
Output is correct |
70 |
Correct |
3 ms |
18780 KB |
Output is correct |
71 |
Correct |
2 ms |
12636 KB |
Output is correct |
72 |
Correct |
1 ms |
4696 KB |
Output is correct |
73 |
Correct |
926 ms |
312072 KB |
Output is correct |
74 |
Correct |
929 ms |
312840 KB |
Output is correct |
75 |
Correct |
1092 ms |
288536 KB |
Output is correct |
76 |
Correct |
904 ms |
287348 KB |
Output is correct |
77 |
Correct |
3576 ms |
434048 KB |
Output is correct |
78 |
Correct |
2585 ms |
263028 KB |
Output is correct |
79 |
Correct |
2773 ms |
304324 KB |
Output is correct |
80 |
Correct |
4800 ms |
416248 KB |
Output is correct |
81 |
Correct |
2656 ms |
263400 KB |
Output is correct |
82 |
Correct |
3770 ms |
361288 KB |
Output is correct |
83 |
Correct |
4906 ms |
416460 KB |
Output is correct |
84 |
Correct |
2515 ms |
289076 KB |
Output is correct |
85 |
Correct |
4705 ms |
463412 KB |
Output is correct |
86 |
Correct |
4636 ms |
455828 KB |
Output is correct |
87 |
Correct |
2174 ms |
348532 KB |
Output is correct |
88 |
Correct |
3671 ms |
481656 KB |
Output is correct |
89 |
Correct |
3701 ms |
482184 KB |
Output is correct |
90 |
Correct |
3721 ms |
482108 KB |
Output is correct |