#include "rect.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define fi first
#define se second
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
struct NOD {
NOD(int sy, int sx, int ey, int ex)
: sy(sy), sx(sx), ey(ey), ex(ex) {}
int sy, sx, ey, ex;
void f(int &_sy, int &_sx, int &_ey, int &_ex) const {
_sy = sy; _sx = sx; _ey = ey; _ex = ex;
}
bool operator < (const NOD &t) const {
if(sy != t.sy) return sy < t.sy;
if(sx != t.sx) return sx < t.sx;
if(ey != t.ey) return ey < t.ey;
return ex < t.ex;
}
bool operator == (const NOD &t) const {
return sy == t.sy && sx == t.sx && ey == t.ey && ex == t.ex;
}
};
const int MX = 4096;
struct SEG {
SEG() { init(); }
int d[MX*2];
void init() { fill(d, d+MX*2, INF); }
void upd(int x, int r) { upmin(d[x+MX], r); }
void cal() { for(int i = MX; i--;) d[i] = min(d[i<<1], d[i<<1|1]); }
int get(int s, int e) {
int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
if(s&1) upmin(r, d[s++]);
if(~e&1) upmin(r, d[e--]);
}
return r;
}
} segu[2505], segd[2505], segl[2505], segr[2505];
vector<NOD> NV;
int myu[2505][2505], myd[2505][2505], myl[2505][2505], myr[2505][2505];
int cou[2505][2505], cod[2505][2505], col[2505][2505], cor[2505][2505];
int A[2505][2505];
int H, W, Ans;
int solve() {
for(int j = 0; j < W; j++) {
vector<pii> V; V.eb(-1, INF);
for(int i = 0, h; i < H; i++) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myu[i][j] = V.back().fi;
V.eb(i, h);
}
V.clear(); V.eb(H, INF);
for(int i = H, h; i--;) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myd[i][j] = V.back().fi;
V.eb(i, h);
}
V.clear(); V.eb(-1, INF);
for(int i = 0, h; i < H; i++) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cou[i][j] = V.back().fi + 1;
V.eb(i, h);
}
V.clear(); V.eb(H, INF);
for(int i = H, h; i--;) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cod[i][j] = V.back().fi - 1;
V.eb(i, h);
}
}
for(int i = 0; i < H; i++) {
vector<pii> V; V.eb(-1, INF);
for(int j = 0, h; j < W; j++) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myl[i][j] = V.back().fi;
V.eb(j, h);
}
V.clear(); V.eb(W, INF);
for(int j = W, h; j--;) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myr[i][j] = V.back().fi;
V.eb(j, h);
}
V.clear(); V.eb(-1, INF);
for(int j = 0, h; j < W; j++) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
col[i][j] = V.back().fi + 1;
V.eb(j, h);
}
V.clear(); V.eb(W, INF);
for(int j = W, h; j--;) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cor[i][j] = V.back().fi - 1;
V.eb(j, h);
}
}
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
segu[i].upd(j, -cou[i][j]);
segd[i].upd(j, cod[i][j]);
segl[j].upd(i, -col[i][j]);
segr[j].upd(i, cor[i][j]);
}
for(int i = 0; i < H; i++) { segu[i].cal(); segd[i].cal(); }
for(int i = 0; i < W; i++) { segl[i].cal(); segr[i].cal(); }
for(int i = 1; i < H-1; i++) for(int j = 1; j < W-1; j++) {
int sy = myu[i][j] + 1, sx = myl[i][j] + 1, ey = myd[i][j] - 1, ex = myr[i][j] - 1;
if(!sy || !sx || H-1 == ey || W-1 == ex) continue;
NV.eb(sy, sx, ey, ex);
}
sorv(NV); univ(NV);
for(auto &hubo : NV) {
int sy, sx, ey, ex; hubo.f(sy, sx, ey, ex);
if(sy < -segu[ey+1].get(sx, ex)) continue;
if(segd[sy-1].get(sx, ex) < ey) continue;
if(sx < -segl[ex+1].get(sy, ey)) continue;
if(segr[sx-1].get(sy, ey) < ex) continue;
Ans++;
}
return Ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
::H = sz(a); ::W = sz(a[0]);
for(int i = 0; i < ::H; i++) for(int j = 0; j < ::W; j++)
::A[i][j] = a[i][j];
return solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
321780 KB |
Output is correct |
2 |
Correct |
276 ms |
322780 KB |
Output is correct |
3 |
Correct |
280 ms |
322736 KB |
Output is correct |
4 |
Correct |
278 ms |
322796 KB |
Output is correct |
5 |
Correct |
277 ms |
322692 KB |
Output is correct |
6 |
Correct |
275 ms |
322736 KB |
Output is correct |
7 |
Correct |
277 ms |
322660 KB |
Output is correct |
8 |
Correct |
277 ms |
322064 KB |
Output is correct |
9 |
Correct |
276 ms |
322820 KB |
Output is correct |
10 |
Correct |
293 ms |
322808 KB |
Output is correct |
11 |
Correct |
322 ms |
322720 KB |
Output is correct |
12 |
Correct |
285 ms |
322936 KB |
Output is correct |
13 |
Correct |
272 ms |
321656 KB |
Output is correct |
14 |
Correct |
301 ms |
322080 KB |
Output is correct |
15 |
Correct |
274 ms |
322040 KB |
Output is correct |
16 |
Correct |
275 ms |
321692 KB |
Output is correct |
17 |
Correct |
273 ms |
321656 KB |
Output is correct |
18 |
Correct |
274 ms |
321676 KB |
Output is correct |
19 |
Correct |
277 ms |
322748 KB |
Output is correct |
20 |
Correct |
276 ms |
322680 KB |
Output is correct |
21 |
Correct |
295 ms |
321984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
321780 KB |
Output is correct |
2 |
Correct |
276 ms |
322780 KB |
Output is correct |
3 |
Correct |
280 ms |
322736 KB |
Output is correct |
4 |
Correct |
278 ms |
322796 KB |
Output is correct |
5 |
Correct |
277 ms |
322692 KB |
Output is correct |
6 |
Correct |
275 ms |
322736 KB |
Output is correct |
7 |
Correct |
277 ms |
322660 KB |
Output is correct |
8 |
Correct |
277 ms |
322064 KB |
Output is correct |
9 |
Correct |
276 ms |
322820 KB |
Output is correct |
10 |
Correct |
293 ms |
322808 KB |
Output is correct |
11 |
Correct |
322 ms |
322720 KB |
Output is correct |
12 |
Correct |
285 ms |
322936 KB |
Output is correct |
13 |
Correct |
272 ms |
321656 KB |
Output is correct |
14 |
Correct |
301 ms |
322080 KB |
Output is correct |
15 |
Correct |
274 ms |
322040 KB |
Output is correct |
16 |
Correct |
275 ms |
321692 KB |
Output is correct |
17 |
Correct |
282 ms |
325180 KB |
Output is correct |
18 |
Correct |
280 ms |
325104 KB |
Output is correct |
19 |
Correct |
280 ms |
325112 KB |
Output is correct |
20 |
Correct |
282 ms |
324992 KB |
Output is correct |
21 |
Correct |
280 ms |
325112 KB |
Output is correct |
22 |
Correct |
289 ms |
325004 KB |
Output is correct |
23 |
Correct |
282 ms |
324984 KB |
Output is correct |
24 |
Correct |
283 ms |
324860 KB |
Output is correct |
25 |
Correct |
273 ms |
321656 KB |
Output is correct |
26 |
Correct |
274 ms |
321676 KB |
Output is correct |
27 |
Correct |
277 ms |
322748 KB |
Output is correct |
28 |
Correct |
276 ms |
322680 KB |
Output is correct |
29 |
Correct |
295 ms |
321984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
321780 KB |
Output is correct |
2 |
Correct |
276 ms |
322780 KB |
Output is correct |
3 |
Correct |
280 ms |
322736 KB |
Output is correct |
4 |
Correct |
278 ms |
322796 KB |
Output is correct |
5 |
Correct |
277 ms |
322692 KB |
Output is correct |
6 |
Correct |
275 ms |
322736 KB |
Output is correct |
7 |
Correct |
277 ms |
322660 KB |
Output is correct |
8 |
Correct |
277 ms |
322064 KB |
Output is correct |
9 |
Correct |
276 ms |
322820 KB |
Output is correct |
10 |
Correct |
293 ms |
322808 KB |
Output is correct |
11 |
Correct |
322 ms |
322720 KB |
Output is correct |
12 |
Correct |
285 ms |
322936 KB |
Output is correct |
13 |
Correct |
272 ms |
321656 KB |
Output is correct |
14 |
Correct |
301 ms |
322080 KB |
Output is correct |
15 |
Correct |
274 ms |
322040 KB |
Output is correct |
16 |
Correct |
275 ms |
321692 KB |
Output is correct |
17 |
Correct |
282 ms |
325180 KB |
Output is correct |
18 |
Correct |
280 ms |
325104 KB |
Output is correct |
19 |
Correct |
280 ms |
325112 KB |
Output is correct |
20 |
Correct |
282 ms |
324992 KB |
Output is correct |
21 |
Correct |
280 ms |
325112 KB |
Output is correct |
22 |
Correct |
289 ms |
325004 KB |
Output is correct |
23 |
Correct |
282 ms |
324984 KB |
Output is correct |
24 |
Correct |
283 ms |
324860 KB |
Output is correct |
25 |
Correct |
302 ms |
331972 KB |
Output is correct |
26 |
Correct |
301 ms |
331892 KB |
Output is correct |
27 |
Correct |
302 ms |
332148 KB |
Output is correct |
28 |
Correct |
300 ms |
331292 KB |
Output is correct |
29 |
Correct |
301 ms |
331884 KB |
Output is correct |
30 |
Correct |
303 ms |
332020 KB |
Output is correct |
31 |
Correct |
306 ms |
331992 KB |
Output is correct |
32 |
Correct |
302 ms |
332000 KB |
Output is correct |
33 |
Correct |
273 ms |
321656 KB |
Output is correct |
34 |
Correct |
274 ms |
321676 KB |
Output is correct |
35 |
Correct |
277 ms |
322748 KB |
Output is correct |
36 |
Correct |
276 ms |
322680 KB |
Output is correct |
37 |
Correct |
295 ms |
321984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
321780 KB |
Output is correct |
2 |
Correct |
276 ms |
322780 KB |
Output is correct |
3 |
Correct |
280 ms |
322736 KB |
Output is correct |
4 |
Correct |
278 ms |
322796 KB |
Output is correct |
5 |
Correct |
277 ms |
322692 KB |
Output is correct |
6 |
Correct |
275 ms |
322736 KB |
Output is correct |
7 |
Correct |
277 ms |
322660 KB |
Output is correct |
8 |
Correct |
277 ms |
322064 KB |
Output is correct |
9 |
Correct |
276 ms |
322820 KB |
Output is correct |
10 |
Correct |
293 ms |
322808 KB |
Output is correct |
11 |
Correct |
322 ms |
322720 KB |
Output is correct |
12 |
Correct |
285 ms |
322936 KB |
Output is correct |
13 |
Correct |
272 ms |
321656 KB |
Output is correct |
14 |
Correct |
301 ms |
322080 KB |
Output is correct |
15 |
Correct |
274 ms |
322040 KB |
Output is correct |
16 |
Correct |
275 ms |
321692 KB |
Output is correct |
17 |
Correct |
282 ms |
325180 KB |
Output is correct |
18 |
Correct |
280 ms |
325104 KB |
Output is correct |
19 |
Correct |
280 ms |
325112 KB |
Output is correct |
20 |
Correct |
282 ms |
324992 KB |
Output is correct |
21 |
Correct |
280 ms |
325112 KB |
Output is correct |
22 |
Correct |
289 ms |
325004 KB |
Output is correct |
23 |
Correct |
282 ms |
324984 KB |
Output is correct |
24 |
Correct |
283 ms |
324860 KB |
Output is correct |
25 |
Correct |
302 ms |
331972 KB |
Output is correct |
26 |
Correct |
301 ms |
331892 KB |
Output is correct |
27 |
Correct |
302 ms |
332148 KB |
Output is correct |
28 |
Correct |
300 ms |
331292 KB |
Output is correct |
29 |
Correct |
301 ms |
331884 KB |
Output is correct |
30 |
Correct |
303 ms |
332020 KB |
Output is correct |
31 |
Correct |
306 ms |
331992 KB |
Output is correct |
32 |
Correct |
302 ms |
332000 KB |
Output is correct |
33 |
Correct |
439 ms |
371200 KB |
Output is correct |
34 |
Correct |
449 ms |
371256 KB |
Output is correct |
35 |
Correct |
450 ms |
371312 KB |
Output is correct |
36 |
Correct |
443 ms |
371344 KB |
Output is correct |
37 |
Correct |
558 ms |
379648 KB |
Output is correct |
38 |
Correct |
564 ms |
379668 KB |
Output is correct |
39 |
Correct |
563 ms |
379996 KB |
Output is correct |
40 |
Correct |
536 ms |
377000 KB |
Output is correct |
41 |
Correct |
490 ms |
373360 KB |
Output is correct |
42 |
Correct |
508 ms |
377436 KB |
Output is correct |
43 |
Correct |
554 ms |
378204 KB |
Output is correct |
44 |
Correct |
558 ms |
380124 KB |
Output is correct |
45 |
Correct |
432 ms |
363652 KB |
Output is correct |
46 |
Correct |
418 ms |
351080 KB |
Output is correct |
47 |
Correct |
561 ms |
379176 KB |
Output is correct |
48 |
Correct |
561 ms |
380124 KB |
Output is correct |
49 |
Correct |
273 ms |
321656 KB |
Output is correct |
50 |
Correct |
274 ms |
321676 KB |
Output is correct |
51 |
Correct |
277 ms |
322748 KB |
Output is correct |
52 |
Correct |
276 ms |
322680 KB |
Output is correct |
53 |
Correct |
295 ms |
321984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
311 ms |
322192 KB |
Output is correct |
2 |
Correct |
306 ms |
322040 KB |
Output is correct |
3 |
Correct |
314 ms |
322072 KB |
Output is correct |
4 |
Correct |
276 ms |
321756 KB |
Output is correct |
5 |
Correct |
312 ms |
322168 KB |
Output is correct |
6 |
Correct |
311 ms |
322040 KB |
Output is correct |
7 |
Correct |
314 ms |
322112 KB |
Output is correct |
8 |
Correct |
316 ms |
322004 KB |
Output is correct |
9 |
Correct |
311 ms |
322044 KB |
Output is correct |
10 |
Correct |
311 ms |
321956 KB |
Output is correct |
11 |
Correct |
310 ms |
321912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
321944 KB |
Output is correct |
2 |
Correct |
1473 ms |
491612 KB |
Output is correct |
3 |
Correct |
2903 ms |
667700 KB |
Output is correct |
4 |
Correct |
2889 ms |
669456 KB |
Output is correct |
5 |
Correct |
2874 ms |
669460 KB |
Output is correct |
6 |
Correct |
1171 ms |
460948 KB |
Output is correct |
7 |
Correct |
1974 ms |
599736 KB |
Output is correct |
8 |
Correct |
2148 ms |
603648 KB |
Output is correct |
9 |
Correct |
273 ms |
321656 KB |
Output is correct |
10 |
Correct |
274 ms |
321676 KB |
Output is correct |
11 |
Correct |
277 ms |
322748 KB |
Output is correct |
12 |
Correct |
276 ms |
322680 KB |
Output is correct |
13 |
Correct |
295 ms |
321984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
321780 KB |
Output is correct |
2 |
Correct |
276 ms |
322780 KB |
Output is correct |
3 |
Correct |
280 ms |
322736 KB |
Output is correct |
4 |
Correct |
278 ms |
322796 KB |
Output is correct |
5 |
Correct |
277 ms |
322692 KB |
Output is correct |
6 |
Correct |
275 ms |
322736 KB |
Output is correct |
7 |
Correct |
277 ms |
322660 KB |
Output is correct |
8 |
Correct |
277 ms |
322064 KB |
Output is correct |
9 |
Correct |
276 ms |
322820 KB |
Output is correct |
10 |
Correct |
293 ms |
322808 KB |
Output is correct |
11 |
Correct |
322 ms |
322720 KB |
Output is correct |
12 |
Correct |
285 ms |
322936 KB |
Output is correct |
13 |
Correct |
272 ms |
321656 KB |
Output is correct |
14 |
Correct |
301 ms |
322080 KB |
Output is correct |
15 |
Correct |
274 ms |
322040 KB |
Output is correct |
16 |
Correct |
275 ms |
321692 KB |
Output is correct |
17 |
Correct |
282 ms |
325180 KB |
Output is correct |
18 |
Correct |
280 ms |
325104 KB |
Output is correct |
19 |
Correct |
280 ms |
325112 KB |
Output is correct |
20 |
Correct |
282 ms |
324992 KB |
Output is correct |
21 |
Correct |
280 ms |
325112 KB |
Output is correct |
22 |
Correct |
289 ms |
325004 KB |
Output is correct |
23 |
Correct |
282 ms |
324984 KB |
Output is correct |
24 |
Correct |
283 ms |
324860 KB |
Output is correct |
25 |
Correct |
302 ms |
331972 KB |
Output is correct |
26 |
Correct |
301 ms |
331892 KB |
Output is correct |
27 |
Correct |
302 ms |
332148 KB |
Output is correct |
28 |
Correct |
300 ms |
331292 KB |
Output is correct |
29 |
Correct |
301 ms |
331884 KB |
Output is correct |
30 |
Correct |
303 ms |
332020 KB |
Output is correct |
31 |
Correct |
306 ms |
331992 KB |
Output is correct |
32 |
Correct |
302 ms |
332000 KB |
Output is correct |
33 |
Correct |
439 ms |
371200 KB |
Output is correct |
34 |
Correct |
449 ms |
371256 KB |
Output is correct |
35 |
Correct |
450 ms |
371312 KB |
Output is correct |
36 |
Correct |
443 ms |
371344 KB |
Output is correct |
37 |
Correct |
558 ms |
379648 KB |
Output is correct |
38 |
Correct |
564 ms |
379668 KB |
Output is correct |
39 |
Correct |
563 ms |
379996 KB |
Output is correct |
40 |
Correct |
536 ms |
377000 KB |
Output is correct |
41 |
Correct |
490 ms |
373360 KB |
Output is correct |
42 |
Correct |
508 ms |
377436 KB |
Output is correct |
43 |
Correct |
554 ms |
378204 KB |
Output is correct |
44 |
Correct |
558 ms |
380124 KB |
Output is correct |
45 |
Correct |
432 ms |
363652 KB |
Output is correct |
46 |
Correct |
418 ms |
351080 KB |
Output is correct |
47 |
Correct |
561 ms |
379176 KB |
Output is correct |
48 |
Correct |
561 ms |
380124 KB |
Output is correct |
49 |
Correct |
311 ms |
322192 KB |
Output is correct |
50 |
Correct |
306 ms |
322040 KB |
Output is correct |
51 |
Correct |
314 ms |
322072 KB |
Output is correct |
52 |
Correct |
276 ms |
321756 KB |
Output is correct |
53 |
Correct |
312 ms |
322168 KB |
Output is correct |
54 |
Correct |
311 ms |
322040 KB |
Output is correct |
55 |
Correct |
314 ms |
322112 KB |
Output is correct |
56 |
Correct |
316 ms |
322004 KB |
Output is correct |
57 |
Correct |
311 ms |
322044 KB |
Output is correct |
58 |
Correct |
311 ms |
321956 KB |
Output is correct |
59 |
Correct |
310 ms |
321912 KB |
Output is correct |
60 |
Correct |
278 ms |
321944 KB |
Output is correct |
61 |
Correct |
1473 ms |
491612 KB |
Output is correct |
62 |
Correct |
2903 ms |
667700 KB |
Output is correct |
63 |
Correct |
2889 ms |
669456 KB |
Output is correct |
64 |
Correct |
2874 ms |
669460 KB |
Output is correct |
65 |
Correct |
1171 ms |
460948 KB |
Output is correct |
66 |
Correct |
1974 ms |
599736 KB |
Output is correct |
67 |
Correct |
2148 ms |
603648 KB |
Output is correct |
68 |
Correct |
2323 ms |
638184 KB |
Output is correct |
69 |
Correct |
2215 ms |
638116 KB |
Output is correct |
70 |
Correct |
2162 ms |
638140 KB |
Output is correct |
71 |
Correct |
2217 ms |
638292 KB |
Output is correct |
72 |
Correct |
4067 ms |
723012 KB |
Output is correct |
73 |
Correct |
2373 ms |
563064 KB |
Output is correct |
74 |
Correct |
2553 ms |
661420 KB |
Output is correct |
75 |
Correct |
3921 ms |
723080 KB |
Output is correct |
76 |
Correct |
2381 ms |
578308 KB |
Output is correct |
77 |
Correct |
3161 ms |
713228 KB |
Output is correct |
78 |
Correct |
3872 ms |
747564 KB |
Output is correct |
79 |
Correct |
2371 ms |
570916 KB |
Output is correct |
80 |
Correct |
3848 ms |
729484 KB |
Output is correct |
81 |
Correct |
3765 ms |
743000 KB |
Output is correct |
82 |
Correct |
2477 ms |
666420 KB |
Output is correct |
83 |
Correct |
3900 ms |
723092 KB |
Output is correct |
84 |
Correct |
3980 ms |
724396 KB |
Output is correct |
85 |
Correct |
4386 ms |
726040 KB |
Output is correct |
86 |
Correct |
273 ms |
321656 KB |
Output is correct |
87 |
Correct |
274 ms |
321676 KB |
Output is correct |
88 |
Correct |
277 ms |
322748 KB |
Output is correct |
89 |
Correct |
276 ms |
322680 KB |
Output is correct |
90 |
Correct |
295 ms |
321984 KB |
Output is correct |