#include "rect.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,a[2505][2505];
int L[2505][2505],R[2505][2505],U[2505][2505],D[2505][2505];
stack <pi> s;
vec N[2505][2505],M[2505][2505];
vector <pair<pi,pi>> V;
void make_LRUD() {
for(int i = 1;i <= n;i++) {
s.push({INF,-1});
for(int j = 1;j <= m;j++) {
while(s.top().x <= a[i][j]) s.pop();
L[i][j] = s.top().y;
s.push({a[i][j],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= n;i++) {
s.push({INF,-1});
for(int j = m;j >= 1;j--) {
while(s.top().x <= a[i][j]) s.pop();
R[i][j] = s.top().y;
s.push({a[i][j],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= m;i++) {
s.push({INF,-1});
for(int j = 1;j <= n;j++) {
while(s.top().x <= a[j][i]) s.pop();
U[j][i] = s.top().y;
s.push({a[j][i],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= m;i++) {
s.push({INF,-1});
for(int j = n;j >= 1;j--) {
while(s.top().x <= a[j][i]) s.pop();
D[j][i] = s.top().y;
s.push({a[j][i],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
if(sx != -1&&ex != -1) N[sx][ex].pb(j);
if(sy != -1&&ey != -1) M[sy][ey].pb(i);
}
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) sort(all(N[i][j])), N[i][j].erase(unique(all(N[i][j])),N[i][j].end());
}
for(int i = 1;i <= m;i++) {
for(int j = 1;j <= m;j++) sort(all(M[i][j])), M[i][j].erase(unique(all(M[i][j])),M[i][j].end());
}
}
ll count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) a[i+1][j+1] = A[i][j];
}
make_LRUD();
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
if(sx == -1||sy == -1||ex == -1||ey == -1) continue;
int L = upper_bound(all(N[sx][ex]),sy)-N[sx][ex].begin();
int R = lower_bound(all(N[sx][ex]),ey)-N[sx][ex].begin()-1;
if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
L = upper_bound(all(M[sy][ey]),sx)-M[sy][ey].begin();
R = lower_bound(all(M[sy][ey]),ex)-M[sy][ey].begin()-1;
if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
V.pb({{sx,sy},{ex,ey}});
}
}
sort(all(V)), V.erase(unique(all(V)),V.end());
return V.size();
}
Compilation message
rect.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
7 | #pragma gcc optimize("O3")
|
rect.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
8 | #pragma gcc optimize("Ofast")
|
rect.cpp:9: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
9 | #pragma gcc optimize("unroll-loops")
|
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
| ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
| ~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
295064 KB |
Output is correct |
2 |
Correct |
160 ms |
295692 KB |
Output is correct |
3 |
Correct |
167 ms |
295652 KB |
Output is correct |
4 |
Correct |
172 ms |
295628 KB |
Output is correct |
5 |
Correct |
171 ms |
295588 KB |
Output is correct |
6 |
Correct |
151 ms |
295640 KB |
Output is correct |
7 |
Correct |
155 ms |
295532 KB |
Output is correct |
8 |
Correct |
171 ms |
295164 KB |
Output is correct |
9 |
Correct |
147 ms |
295628 KB |
Output is correct |
10 |
Correct |
155 ms |
295616 KB |
Output is correct |
11 |
Correct |
158 ms |
295576 KB |
Output is correct |
12 |
Correct |
152 ms |
295584 KB |
Output is correct |
13 |
Correct |
144 ms |
294932 KB |
Output is correct |
14 |
Correct |
158 ms |
295132 KB |
Output is correct |
15 |
Correct |
178 ms |
295216 KB |
Output is correct |
16 |
Correct |
167 ms |
294968 KB |
Output is correct |
17 |
Correct |
173 ms |
295048 KB |
Output is correct |
18 |
Correct |
172 ms |
294940 KB |
Output is correct |
19 |
Correct |
156 ms |
295620 KB |
Output is correct |
20 |
Correct |
161 ms |
295556 KB |
Output is correct |
21 |
Correct |
152 ms |
295156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
295064 KB |
Output is correct |
2 |
Correct |
160 ms |
295692 KB |
Output is correct |
3 |
Correct |
167 ms |
295652 KB |
Output is correct |
4 |
Correct |
172 ms |
295628 KB |
Output is correct |
5 |
Correct |
171 ms |
295588 KB |
Output is correct |
6 |
Correct |
151 ms |
295640 KB |
Output is correct |
7 |
Correct |
155 ms |
295532 KB |
Output is correct |
8 |
Correct |
171 ms |
295164 KB |
Output is correct |
9 |
Correct |
147 ms |
295628 KB |
Output is correct |
10 |
Correct |
155 ms |
295616 KB |
Output is correct |
11 |
Correct |
158 ms |
295576 KB |
Output is correct |
12 |
Correct |
152 ms |
295584 KB |
Output is correct |
13 |
Correct |
144 ms |
294932 KB |
Output is correct |
14 |
Correct |
158 ms |
295132 KB |
Output is correct |
15 |
Correct |
178 ms |
295216 KB |
Output is correct |
16 |
Correct |
167 ms |
294968 KB |
Output is correct |
17 |
Correct |
173 ms |
295048 KB |
Output is correct |
18 |
Correct |
172 ms |
294940 KB |
Output is correct |
19 |
Correct |
156 ms |
295620 KB |
Output is correct |
20 |
Correct |
161 ms |
295556 KB |
Output is correct |
21 |
Correct |
152 ms |
295156 KB |
Output is correct |
22 |
Correct |
170 ms |
297060 KB |
Output is correct |
23 |
Correct |
167 ms |
297084 KB |
Output is correct |
24 |
Correct |
161 ms |
297120 KB |
Output is correct |
25 |
Correct |
160 ms |
296784 KB |
Output is correct |
26 |
Correct |
152 ms |
296932 KB |
Output is correct |
27 |
Correct |
174 ms |
296928 KB |
Output is correct |
28 |
Correct |
166 ms |
297024 KB |
Output is correct |
29 |
Correct |
156 ms |
296728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
295064 KB |
Output is correct |
2 |
Correct |
160 ms |
295692 KB |
Output is correct |
3 |
Correct |
167 ms |
295652 KB |
Output is correct |
4 |
Correct |
172 ms |
295628 KB |
Output is correct |
5 |
Correct |
171 ms |
295588 KB |
Output is correct |
6 |
Correct |
151 ms |
295640 KB |
Output is correct |
7 |
Correct |
155 ms |
295532 KB |
Output is correct |
8 |
Correct |
171 ms |
295164 KB |
Output is correct |
9 |
Correct |
147 ms |
295628 KB |
Output is correct |
10 |
Correct |
155 ms |
295616 KB |
Output is correct |
11 |
Correct |
158 ms |
295576 KB |
Output is correct |
12 |
Correct |
152 ms |
295584 KB |
Output is correct |
13 |
Correct |
144 ms |
294932 KB |
Output is correct |
14 |
Correct |
158 ms |
295132 KB |
Output is correct |
15 |
Correct |
178 ms |
295216 KB |
Output is correct |
16 |
Correct |
167 ms |
294968 KB |
Output is correct |
17 |
Correct |
170 ms |
297060 KB |
Output is correct |
18 |
Correct |
167 ms |
297084 KB |
Output is correct |
19 |
Correct |
161 ms |
297120 KB |
Output is correct |
20 |
Correct |
160 ms |
296784 KB |
Output is correct |
21 |
Correct |
152 ms |
296932 KB |
Output is correct |
22 |
Correct |
174 ms |
296928 KB |
Output is correct |
23 |
Correct |
166 ms |
297024 KB |
Output is correct |
24 |
Correct |
156 ms |
296728 KB |
Output is correct |
25 |
Correct |
173 ms |
295048 KB |
Output is correct |
26 |
Correct |
172 ms |
294940 KB |
Output is correct |
27 |
Correct |
156 ms |
295620 KB |
Output is correct |
28 |
Correct |
161 ms |
295556 KB |
Output is correct |
29 |
Correct |
152 ms |
295156 KB |
Output is correct |
30 |
Correct |
178 ms |
301904 KB |
Output is correct |
31 |
Correct |
173 ms |
301888 KB |
Output is correct |
32 |
Correct |
169 ms |
301908 KB |
Output is correct |
33 |
Correct |
182 ms |
300684 KB |
Output is correct |
34 |
Correct |
189 ms |
301284 KB |
Output is correct |
35 |
Correct |
193 ms |
301372 KB |
Output is correct |
36 |
Correct |
189 ms |
301492 KB |
Output is correct |
37 |
Correct |
181 ms |
301324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
295064 KB |
Output is correct |
2 |
Correct |
160 ms |
295692 KB |
Output is correct |
3 |
Correct |
167 ms |
295652 KB |
Output is correct |
4 |
Correct |
172 ms |
295628 KB |
Output is correct |
5 |
Correct |
171 ms |
295588 KB |
Output is correct |
6 |
Correct |
151 ms |
295640 KB |
Output is correct |
7 |
Correct |
155 ms |
295532 KB |
Output is correct |
8 |
Correct |
171 ms |
295164 KB |
Output is correct |
9 |
Correct |
147 ms |
295628 KB |
Output is correct |
10 |
Correct |
155 ms |
295616 KB |
Output is correct |
11 |
Correct |
158 ms |
295576 KB |
Output is correct |
12 |
Correct |
152 ms |
295584 KB |
Output is correct |
13 |
Correct |
144 ms |
294932 KB |
Output is correct |
14 |
Correct |
158 ms |
295132 KB |
Output is correct |
15 |
Correct |
178 ms |
295216 KB |
Output is correct |
16 |
Correct |
167 ms |
294968 KB |
Output is correct |
17 |
Correct |
170 ms |
297060 KB |
Output is correct |
18 |
Correct |
167 ms |
297084 KB |
Output is correct |
19 |
Correct |
161 ms |
297120 KB |
Output is correct |
20 |
Correct |
160 ms |
296784 KB |
Output is correct |
21 |
Correct |
152 ms |
296932 KB |
Output is correct |
22 |
Correct |
174 ms |
296928 KB |
Output is correct |
23 |
Correct |
166 ms |
297024 KB |
Output is correct |
24 |
Correct |
156 ms |
296728 KB |
Output is correct |
25 |
Correct |
178 ms |
301904 KB |
Output is correct |
26 |
Correct |
173 ms |
301888 KB |
Output is correct |
27 |
Correct |
169 ms |
301908 KB |
Output is correct |
28 |
Correct |
182 ms |
300684 KB |
Output is correct |
29 |
Correct |
189 ms |
301284 KB |
Output is correct |
30 |
Correct |
193 ms |
301372 KB |
Output is correct |
31 |
Correct |
189 ms |
301492 KB |
Output is correct |
32 |
Correct |
181 ms |
301324 KB |
Output is correct |
33 |
Correct |
173 ms |
295048 KB |
Output is correct |
34 |
Correct |
172 ms |
294940 KB |
Output is correct |
35 |
Correct |
156 ms |
295620 KB |
Output is correct |
36 |
Correct |
161 ms |
295556 KB |
Output is correct |
37 |
Correct |
152 ms |
295156 KB |
Output is correct |
38 |
Correct |
276 ms |
340864 KB |
Output is correct |
39 |
Correct |
272 ms |
340944 KB |
Output is correct |
40 |
Correct |
293 ms |
340932 KB |
Output is correct |
41 |
Correct |
298 ms |
340864 KB |
Output is correct |
42 |
Correct |
347 ms |
339748 KB |
Output is correct |
43 |
Correct |
367 ms |
339760 KB |
Output is correct |
44 |
Correct |
362 ms |
340120 KB |
Output is correct |
45 |
Correct |
385 ms |
338048 KB |
Output is correct |
46 |
Correct |
292 ms |
327096 KB |
Output is correct |
47 |
Correct |
324 ms |
328464 KB |
Output is correct |
48 |
Correct |
405 ms |
334888 KB |
Output is correct |
49 |
Correct |
419 ms |
336952 KB |
Output is correct |
50 |
Correct |
319 ms |
323176 KB |
Output is correct |
51 |
Correct |
287 ms |
316148 KB |
Output is correct |
52 |
Correct |
384 ms |
335200 KB |
Output is correct |
53 |
Correct |
419 ms |
336148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
213 ms |
295500 KB |
Output is correct |
2 |
Correct |
183 ms |
295396 KB |
Output is correct |
3 |
Correct |
221 ms |
295256 KB |
Output is correct |
4 |
Correct |
180 ms |
295040 KB |
Output is correct |
5 |
Correct |
189 ms |
295460 KB |
Output is correct |
6 |
Correct |
198 ms |
295496 KB |
Output is correct |
7 |
Correct |
187 ms |
295512 KB |
Output is correct |
8 |
Correct |
202 ms |
295380 KB |
Output is correct |
9 |
Correct |
193 ms |
295436 KB |
Output is correct |
10 |
Correct |
167 ms |
295192 KB |
Output is correct |
11 |
Correct |
182 ms |
295244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
295048 KB |
Output is correct |
2 |
Correct |
172 ms |
294940 KB |
Output is correct |
3 |
Correct |
156 ms |
295620 KB |
Output is correct |
4 |
Correct |
161 ms |
295556 KB |
Output is correct |
5 |
Correct |
152 ms |
295156 KB |
Output is correct |
6 |
Correct |
142 ms |
295172 KB |
Output is correct |
7 |
Correct |
728 ms |
406780 KB |
Output is correct |
8 |
Correct |
1467 ms |
524928 KB |
Output is correct |
9 |
Correct |
1417 ms |
526040 KB |
Output is correct |
10 |
Correct |
1469 ms |
525928 KB |
Output is correct |
11 |
Correct |
417 ms |
385804 KB |
Output is correct |
12 |
Correct |
647 ms |
475064 KB |
Output is correct |
13 |
Correct |
747 ms |
478832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
295064 KB |
Output is correct |
2 |
Correct |
160 ms |
295692 KB |
Output is correct |
3 |
Correct |
167 ms |
295652 KB |
Output is correct |
4 |
Correct |
172 ms |
295628 KB |
Output is correct |
5 |
Correct |
171 ms |
295588 KB |
Output is correct |
6 |
Correct |
151 ms |
295640 KB |
Output is correct |
7 |
Correct |
155 ms |
295532 KB |
Output is correct |
8 |
Correct |
171 ms |
295164 KB |
Output is correct |
9 |
Correct |
147 ms |
295628 KB |
Output is correct |
10 |
Correct |
155 ms |
295616 KB |
Output is correct |
11 |
Correct |
158 ms |
295576 KB |
Output is correct |
12 |
Correct |
152 ms |
295584 KB |
Output is correct |
13 |
Correct |
144 ms |
294932 KB |
Output is correct |
14 |
Correct |
158 ms |
295132 KB |
Output is correct |
15 |
Correct |
178 ms |
295216 KB |
Output is correct |
16 |
Correct |
167 ms |
294968 KB |
Output is correct |
17 |
Correct |
170 ms |
297060 KB |
Output is correct |
18 |
Correct |
167 ms |
297084 KB |
Output is correct |
19 |
Correct |
161 ms |
297120 KB |
Output is correct |
20 |
Correct |
160 ms |
296784 KB |
Output is correct |
21 |
Correct |
152 ms |
296932 KB |
Output is correct |
22 |
Correct |
174 ms |
296928 KB |
Output is correct |
23 |
Correct |
166 ms |
297024 KB |
Output is correct |
24 |
Correct |
156 ms |
296728 KB |
Output is correct |
25 |
Correct |
178 ms |
301904 KB |
Output is correct |
26 |
Correct |
173 ms |
301888 KB |
Output is correct |
27 |
Correct |
169 ms |
301908 KB |
Output is correct |
28 |
Correct |
182 ms |
300684 KB |
Output is correct |
29 |
Correct |
189 ms |
301284 KB |
Output is correct |
30 |
Correct |
193 ms |
301372 KB |
Output is correct |
31 |
Correct |
189 ms |
301492 KB |
Output is correct |
32 |
Correct |
181 ms |
301324 KB |
Output is correct |
33 |
Correct |
276 ms |
340864 KB |
Output is correct |
34 |
Correct |
272 ms |
340944 KB |
Output is correct |
35 |
Correct |
293 ms |
340932 KB |
Output is correct |
36 |
Correct |
298 ms |
340864 KB |
Output is correct |
37 |
Correct |
347 ms |
339748 KB |
Output is correct |
38 |
Correct |
367 ms |
339760 KB |
Output is correct |
39 |
Correct |
362 ms |
340120 KB |
Output is correct |
40 |
Correct |
385 ms |
338048 KB |
Output is correct |
41 |
Correct |
292 ms |
327096 KB |
Output is correct |
42 |
Correct |
324 ms |
328464 KB |
Output is correct |
43 |
Correct |
405 ms |
334888 KB |
Output is correct |
44 |
Correct |
419 ms |
336952 KB |
Output is correct |
45 |
Correct |
319 ms |
323176 KB |
Output is correct |
46 |
Correct |
287 ms |
316148 KB |
Output is correct |
47 |
Correct |
384 ms |
335200 KB |
Output is correct |
48 |
Correct |
419 ms |
336148 KB |
Output is correct |
49 |
Correct |
213 ms |
295500 KB |
Output is correct |
50 |
Correct |
183 ms |
295396 KB |
Output is correct |
51 |
Correct |
221 ms |
295256 KB |
Output is correct |
52 |
Correct |
180 ms |
295040 KB |
Output is correct |
53 |
Correct |
189 ms |
295460 KB |
Output is correct |
54 |
Correct |
198 ms |
295496 KB |
Output is correct |
55 |
Correct |
187 ms |
295512 KB |
Output is correct |
56 |
Correct |
202 ms |
295380 KB |
Output is correct |
57 |
Correct |
193 ms |
295436 KB |
Output is correct |
58 |
Correct |
167 ms |
295192 KB |
Output is correct |
59 |
Correct |
182 ms |
295244 KB |
Output is correct |
60 |
Correct |
142 ms |
295172 KB |
Output is correct |
61 |
Correct |
728 ms |
406780 KB |
Output is correct |
62 |
Correct |
1467 ms |
524928 KB |
Output is correct |
63 |
Correct |
1417 ms |
526040 KB |
Output is correct |
64 |
Correct |
1469 ms |
525928 KB |
Output is correct |
65 |
Correct |
417 ms |
385804 KB |
Output is correct |
66 |
Correct |
647 ms |
475064 KB |
Output is correct |
67 |
Correct |
747 ms |
478832 KB |
Output is correct |
68 |
Correct |
173 ms |
295048 KB |
Output is correct |
69 |
Correct |
172 ms |
294940 KB |
Output is correct |
70 |
Correct |
156 ms |
295620 KB |
Output is correct |
71 |
Correct |
161 ms |
295556 KB |
Output is correct |
72 |
Correct |
152 ms |
295156 KB |
Output is correct |
73 |
Correct |
1377 ms |
709016 KB |
Output is correct |
74 |
Correct |
1129 ms |
709136 KB |
Output is correct |
75 |
Correct |
1602 ms |
709084 KB |
Output is correct |
76 |
Correct |
1373 ms |
708996 KB |
Output is correct |
77 |
Correct |
2450 ms |
718432 KB |
Output is correct |
78 |
Correct |
1654 ms |
490892 KB |
Output is correct |
79 |
Correct |
1743 ms |
556120 KB |
Output is correct |
80 |
Correct |
2766 ms |
629664 KB |
Output is correct |
81 |
Correct |
1914 ms |
507096 KB |
Output is correct |
82 |
Correct |
2674 ms |
592424 KB |
Output is correct |
83 |
Correct |
3268 ms |
656516 KB |
Output is correct |
84 |
Correct |
2081 ms |
495088 KB |
Output is correct |
85 |
Correct |
3360 ms |
652448 KB |
Output is correct |
86 |
Correct |
3366 ms |
644512 KB |
Output is correct |
87 |
Correct |
1679 ms |
584180 KB |
Output is correct |
88 |
Correct |
2966 ms |
718428 KB |
Output is correct |
89 |
Correct |
2852 ms |
718284 KB |
Output is correct |
90 |
Correct |
2875 ms |
718452 KB |
Output is correct |