#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int16_t,2>;
const int mxN = 2502;
int n, m;
bitset<mxN> grid[mxN];
vector<int16_t> row[mxN][mxN], col[mxN][mxN];
deque<ar2> lines[mxN];
vector<int16_t> grid2[mxN];
int16_t R[mxN][mxN];
struct Fenwick2D{
int fen[mxN][mxN];
void init(int n, int m){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
fen[i][j]=0;
}
void upd(int _x, int _y, int v){
_x++, _y++;
for(int x = _x; x<mxN; x+=x&-x)
for(int y = _y; y < mxN; y+=y&-y)
fen[x][y]+=v;
}
int sum(int _x, int _y){
int s = 0; _x++, _y++;
for(int x = _x; x>0; x-=x&-x)
for(int y = _y; y>0; y-=y&-y)
s+=fen[x][y];
return s;
}
int sum(int x1, int y1, int x2, int y2){
return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
}
} fen2d;
ll count_rectangles(vector<vi> a) {
n = sz(a); m = sz(a[0]); ll ans = 0;
for(int i = 0; i < n; i++){
stack<int> S = stack<int>();
for(int j = m-1; j >= 0; j--){
while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
if(sz(S) and abs(S.top()-j)>1)
row[i][j].pb(S.top());
S.push(j);
}
S = stack<int>();
for(int j = 0; j < m; j++){
while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
if(sz(S) and abs(S.top()-j)>1)
if(a[i][S.top()]!=a[i][j])
row[i][S.top()].pb(j);
S.push(j);
}
}
for(int j = 0; j < m; j++){
stack<int> S = stack<int>();
for(int i = n-1; i >= 0; i--){
while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
if(sz(S) and abs(S.top()-i)>1)
col[i][j].pb(S.top());
S.push(i);
}
S = stack<int>();
for(int i = 0; i < n; i++){
while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
if(sz(S) and abs(S.top()-i)>1)
if(a[S.top()][j]!=a[i][j])
col[S.top()][j].pb(i);
S.push(i);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
sort(all(row[i][j])), sort(all(col[i][j]));
fen2d.init(n,m);
for(int i = 1; i < n-1; i++){
for(int j = 0; j < m; j++)
for(auto u : col[i-1][j])
grid[u][j]=1, grid2[u].pb(j);
for(int k = 0; k < n; k++){
for(auto u : grid2[k]){
int y = u;
if(!y or !grid[k][y-1]){
while(y<m-1 and grid[k][y+1]) y++;
lines[u].pb({k,y});
}
}
}
for(auto [x,y] : lines[0]) fen2d.upd(x,y,1);
for(int j = 0; j < m; j++){
for(auto [x,y] : lines[j+1]) fen2d.upd(x,y,1);
for(auto k : row[i][j]){
if(i==1 or !binary_search(all(row[i-1][j]),k)){
R[j][k] = i+1;
while(R[j][k]<n and binary_search(all(row[R[j][k]][j]),k)) R[j][k]++;
}
int xd = fen2d.sum(i+1,k-1,R[j][k],mxN-2); ans+=xd;
}
for(auto u : col[i-1][j]) grid[u][j]=0;
}
for(int j = 0; j < m; j++){
for(auto [x,y] : lines[j]) fen2d.upd(x,y,-1);
lines[j].clear();
}
for(int k = 0; k < n; k++) grid2[k].clear();
}
return ans;
}
Compilation message
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:96:34: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
96 | lines[u].pb({k,y});
| ^
rect.cpp:96:36: warning: narrowing conversion of 'y' from 'int' to 'short int' [-Wnarrowing]
96 | lines[u].pb({k,y});
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
296292 KB |
Output is correct |
2 |
Correct |
119 ms |
296596 KB |
Output is correct |
3 |
Correct |
137 ms |
296528 KB |
Output is correct |
4 |
Correct |
124 ms |
296532 KB |
Output is correct |
5 |
Correct |
116 ms |
296272 KB |
Output is correct |
6 |
Correct |
119 ms |
296744 KB |
Output is correct |
7 |
Correct |
137 ms |
296784 KB |
Output is correct |
8 |
Correct |
143 ms |
296432 KB |
Output is correct |
9 |
Correct |
119 ms |
296708 KB |
Output is correct |
10 |
Correct |
119 ms |
296532 KB |
Output is correct |
11 |
Correct |
143 ms |
296528 KB |
Output is correct |
12 |
Correct |
118 ms |
296532 KB |
Output is correct |
13 |
Correct |
151 ms |
296004 KB |
Output is correct |
14 |
Correct |
125 ms |
296276 KB |
Output is correct |
15 |
Correct |
122 ms |
296016 KB |
Output is correct |
16 |
Correct |
121 ms |
296276 KB |
Output is correct |
17 |
Correct |
125 ms |
296016 KB |
Output is correct |
18 |
Correct |
119 ms |
296184 KB |
Output is correct |
19 |
Correct |
123 ms |
296552 KB |
Output is correct |
20 |
Correct |
127 ms |
296232 KB |
Output is correct |
21 |
Correct |
121 ms |
296064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
296292 KB |
Output is correct |
2 |
Correct |
119 ms |
296596 KB |
Output is correct |
3 |
Correct |
137 ms |
296528 KB |
Output is correct |
4 |
Correct |
124 ms |
296532 KB |
Output is correct |
5 |
Correct |
116 ms |
296272 KB |
Output is correct |
6 |
Correct |
119 ms |
296744 KB |
Output is correct |
7 |
Correct |
137 ms |
296784 KB |
Output is correct |
8 |
Correct |
143 ms |
296432 KB |
Output is correct |
9 |
Correct |
119 ms |
296708 KB |
Output is correct |
10 |
Correct |
119 ms |
296532 KB |
Output is correct |
11 |
Correct |
143 ms |
296528 KB |
Output is correct |
12 |
Correct |
118 ms |
296532 KB |
Output is correct |
13 |
Correct |
151 ms |
296004 KB |
Output is correct |
14 |
Correct |
125 ms |
296276 KB |
Output is correct |
15 |
Correct |
122 ms |
296016 KB |
Output is correct |
16 |
Correct |
121 ms |
296276 KB |
Output is correct |
17 |
Correct |
125 ms |
296016 KB |
Output is correct |
18 |
Correct |
119 ms |
296184 KB |
Output is correct |
19 |
Correct |
123 ms |
296552 KB |
Output is correct |
20 |
Correct |
127 ms |
296232 KB |
Output is correct |
21 |
Correct |
121 ms |
296064 KB |
Output is correct |
22 |
Correct |
121 ms |
297416 KB |
Output is correct |
23 |
Correct |
143 ms |
297368 KB |
Output is correct |
24 |
Correct |
119 ms |
297296 KB |
Output is correct |
25 |
Correct |
124 ms |
297552 KB |
Output is correct |
26 |
Correct |
127 ms |
297552 KB |
Output is correct |
27 |
Correct |
126 ms |
297608 KB |
Output is correct |
28 |
Correct |
118 ms |
297536 KB |
Output is correct |
29 |
Correct |
128 ms |
297252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
296292 KB |
Output is correct |
2 |
Correct |
119 ms |
296596 KB |
Output is correct |
3 |
Correct |
137 ms |
296528 KB |
Output is correct |
4 |
Correct |
124 ms |
296532 KB |
Output is correct |
5 |
Correct |
116 ms |
296272 KB |
Output is correct |
6 |
Correct |
119 ms |
296744 KB |
Output is correct |
7 |
Correct |
137 ms |
296784 KB |
Output is correct |
8 |
Correct |
143 ms |
296432 KB |
Output is correct |
9 |
Correct |
119 ms |
296708 KB |
Output is correct |
10 |
Correct |
119 ms |
296532 KB |
Output is correct |
11 |
Correct |
143 ms |
296528 KB |
Output is correct |
12 |
Correct |
118 ms |
296532 KB |
Output is correct |
13 |
Correct |
151 ms |
296004 KB |
Output is correct |
14 |
Correct |
125 ms |
296276 KB |
Output is correct |
15 |
Correct |
122 ms |
296016 KB |
Output is correct |
16 |
Correct |
121 ms |
296276 KB |
Output is correct |
17 |
Correct |
121 ms |
297416 KB |
Output is correct |
18 |
Correct |
143 ms |
297368 KB |
Output is correct |
19 |
Correct |
119 ms |
297296 KB |
Output is correct |
20 |
Correct |
124 ms |
297552 KB |
Output is correct |
21 |
Correct |
127 ms |
297552 KB |
Output is correct |
22 |
Correct |
126 ms |
297608 KB |
Output is correct |
23 |
Correct |
118 ms |
297536 KB |
Output is correct |
24 |
Correct |
128 ms |
297252 KB |
Output is correct |
25 |
Correct |
125 ms |
296016 KB |
Output is correct |
26 |
Correct |
119 ms |
296184 KB |
Output is correct |
27 |
Correct |
123 ms |
296552 KB |
Output is correct |
28 |
Correct |
127 ms |
296232 KB |
Output is correct |
29 |
Correct |
121 ms |
296064 KB |
Output is correct |
30 |
Correct |
131 ms |
301020 KB |
Output is correct |
31 |
Correct |
128 ms |
300852 KB |
Output is correct |
32 |
Correct |
132 ms |
301052 KB |
Output is correct |
33 |
Correct |
140 ms |
300112 KB |
Output is correct |
34 |
Correct |
139 ms |
300880 KB |
Output is correct |
35 |
Correct |
137 ms |
300884 KB |
Output is correct |
36 |
Correct |
163 ms |
300852 KB |
Output is correct |
37 |
Correct |
138 ms |
300776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
296292 KB |
Output is correct |
2 |
Correct |
119 ms |
296596 KB |
Output is correct |
3 |
Correct |
137 ms |
296528 KB |
Output is correct |
4 |
Correct |
124 ms |
296532 KB |
Output is correct |
5 |
Correct |
116 ms |
296272 KB |
Output is correct |
6 |
Correct |
119 ms |
296744 KB |
Output is correct |
7 |
Correct |
137 ms |
296784 KB |
Output is correct |
8 |
Correct |
143 ms |
296432 KB |
Output is correct |
9 |
Correct |
119 ms |
296708 KB |
Output is correct |
10 |
Correct |
119 ms |
296532 KB |
Output is correct |
11 |
Correct |
143 ms |
296528 KB |
Output is correct |
12 |
Correct |
118 ms |
296532 KB |
Output is correct |
13 |
Correct |
151 ms |
296004 KB |
Output is correct |
14 |
Correct |
125 ms |
296276 KB |
Output is correct |
15 |
Correct |
122 ms |
296016 KB |
Output is correct |
16 |
Correct |
121 ms |
296276 KB |
Output is correct |
17 |
Correct |
121 ms |
297416 KB |
Output is correct |
18 |
Correct |
143 ms |
297368 KB |
Output is correct |
19 |
Correct |
119 ms |
297296 KB |
Output is correct |
20 |
Correct |
124 ms |
297552 KB |
Output is correct |
21 |
Correct |
127 ms |
297552 KB |
Output is correct |
22 |
Correct |
126 ms |
297608 KB |
Output is correct |
23 |
Correct |
118 ms |
297536 KB |
Output is correct |
24 |
Correct |
128 ms |
297252 KB |
Output is correct |
25 |
Correct |
131 ms |
301020 KB |
Output is correct |
26 |
Correct |
128 ms |
300852 KB |
Output is correct |
27 |
Correct |
132 ms |
301052 KB |
Output is correct |
28 |
Correct |
140 ms |
300112 KB |
Output is correct |
29 |
Correct |
139 ms |
300880 KB |
Output is correct |
30 |
Correct |
137 ms |
300884 KB |
Output is correct |
31 |
Correct |
163 ms |
300852 KB |
Output is correct |
32 |
Correct |
138 ms |
300776 KB |
Output is correct |
33 |
Correct |
125 ms |
296016 KB |
Output is correct |
34 |
Correct |
119 ms |
296184 KB |
Output is correct |
35 |
Correct |
123 ms |
296552 KB |
Output is correct |
36 |
Correct |
127 ms |
296232 KB |
Output is correct |
37 |
Correct |
121 ms |
296064 KB |
Output is correct |
38 |
Correct |
230 ms |
328784 KB |
Output is correct |
39 |
Correct |
241 ms |
321872 KB |
Output is correct |
40 |
Correct |
207 ms |
321876 KB |
Output is correct |
41 |
Correct |
201 ms |
314960 KB |
Output is correct |
42 |
Correct |
252 ms |
341328 KB |
Output is correct |
43 |
Correct |
247 ms |
341280 KB |
Output is correct |
44 |
Correct |
259 ms |
341764 KB |
Output is correct |
45 |
Correct |
252 ms |
338920 KB |
Output is correct |
46 |
Correct |
214 ms |
318744 KB |
Output is correct |
47 |
Correct |
248 ms |
321340 KB |
Output is correct |
48 |
Correct |
440 ms |
327768 KB |
Output is correct |
49 |
Correct |
357 ms |
329736 KB |
Output is correct |
50 |
Correct |
244 ms |
316496 KB |
Output is correct |
51 |
Correct |
242 ms |
314536 KB |
Output is correct |
52 |
Correct |
313 ms |
327248 KB |
Output is correct |
53 |
Correct |
337 ms |
328272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
306516 KB |
Output is correct |
2 |
Correct |
150 ms |
304980 KB |
Output is correct |
3 |
Correct |
125 ms |
296068 KB |
Output is correct |
4 |
Correct |
126 ms |
296280 KB |
Output is correct |
5 |
Correct |
126 ms |
301476 KB |
Output is correct |
6 |
Correct |
166 ms |
301652 KB |
Output is correct |
7 |
Correct |
134 ms |
301608 KB |
Output is correct |
8 |
Correct |
129 ms |
301168 KB |
Output is correct |
9 |
Correct |
140 ms |
301004 KB |
Output is correct |
10 |
Correct |
113 ms |
296272 KB |
Output is correct |
11 |
Correct |
114 ms |
296272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
296016 KB |
Output is correct |
2 |
Correct |
119 ms |
296184 KB |
Output is correct |
3 |
Correct |
123 ms |
296552 KB |
Output is correct |
4 |
Correct |
127 ms |
296232 KB |
Output is correct |
5 |
Correct |
121 ms |
296064 KB |
Output is correct |
6 |
Correct |
115 ms |
296316 KB |
Output is correct |
7 |
Correct |
645 ms |
392280 KB |
Output is correct |
8 |
Correct |
1383 ms |
492328 KB |
Output is correct |
9 |
Correct |
1316 ms |
493156 KB |
Output is correct |
10 |
Correct |
1382 ms |
493268 KB |
Output is correct |
11 |
Correct |
246 ms |
338504 KB |
Output is correct |
12 |
Correct |
391 ms |
378196 KB |
Output is correct |
13 |
Correct |
436 ms |
381972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
296292 KB |
Output is correct |
2 |
Correct |
119 ms |
296596 KB |
Output is correct |
3 |
Correct |
137 ms |
296528 KB |
Output is correct |
4 |
Correct |
124 ms |
296532 KB |
Output is correct |
5 |
Correct |
116 ms |
296272 KB |
Output is correct |
6 |
Correct |
119 ms |
296744 KB |
Output is correct |
7 |
Correct |
137 ms |
296784 KB |
Output is correct |
8 |
Correct |
143 ms |
296432 KB |
Output is correct |
9 |
Correct |
119 ms |
296708 KB |
Output is correct |
10 |
Correct |
119 ms |
296532 KB |
Output is correct |
11 |
Correct |
143 ms |
296528 KB |
Output is correct |
12 |
Correct |
118 ms |
296532 KB |
Output is correct |
13 |
Correct |
151 ms |
296004 KB |
Output is correct |
14 |
Correct |
125 ms |
296276 KB |
Output is correct |
15 |
Correct |
122 ms |
296016 KB |
Output is correct |
16 |
Correct |
121 ms |
296276 KB |
Output is correct |
17 |
Correct |
121 ms |
297416 KB |
Output is correct |
18 |
Correct |
143 ms |
297368 KB |
Output is correct |
19 |
Correct |
119 ms |
297296 KB |
Output is correct |
20 |
Correct |
124 ms |
297552 KB |
Output is correct |
21 |
Correct |
127 ms |
297552 KB |
Output is correct |
22 |
Correct |
126 ms |
297608 KB |
Output is correct |
23 |
Correct |
118 ms |
297536 KB |
Output is correct |
24 |
Correct |
128 ms |
297252 KB |
Output is correct |
25 |
Correct |
131 ms |
301020 KB |
Output is correct |
26 |
Correct |
128 ms |
300852 KB |
Output is correct |
27 |
Correct |
132 ms |
301052 KB |
Output is correct |
28 |
Correct |
140 ms |
300112 KB |
Output is correct |
29 |
Correct |
139 ms |
300880 KB |
Output is correct |
30 |
Correct |
137 ms |
300884 KB |
Output is correct |
31 |
Correct |
163 ms |
300852 KB |
Output is correct |
32 |
Correct |
138 ms |
300776 KB |
Output is correct |
33 |
Correct |
230 ms |
328784 KB |
Output is correct |
34 |
Correct |
241 ms |
321872 KB |
Output is correct |
35 |
Correct |
207 ms |
321876 KB |
Output is correct |
36 |
Correct |
201 ms |
314960 KB |
Output is correct |
37 |
Correct |
252 ms |
341328 KB |
Output is correct |
38 |
Correct |
247 ms |
341280 KB |
Output is correct |
39 |
Correct |
259 ms |
341764 KB |
Output is correct |
40 |
Correct |
252 ms |
338920 KB |
Output is correct |
41 |
Correct |
214 ms |
318744 KB |
Output is correct |
42 |
Correct |
248 ms |
321340 KB |
Output is correct |
43 |
Correct |
440 ms |
327768 KB |
Output is correct |
44 |
Correct |
357 ms |
329736 KB |
Output is correct |
45 |
Correct |
244 ms |
316496 KB |
Output is correct |
46 |
Correct |
242 ms |
314536 KB |
Output is correct |
47 |
Correct |
313 ms |
327248 KB |
Output is correct |
48 |
Correct |
337 ms |
328272 KB |
Output is correct |
49 |
Correct |
123 ms |
306516 KB |
Output is correct |
50 |
Correct |
150 ms |
304980 KB |
Output is correct |
51 |
Correct |
125 ms |
296068 KB |
Output is correct |
52 |
Correct |
126 ms |
296280 KB |
Output is correct |
53 |
Correct |
126 ms |
301476 KB |
Output is correct |
54 |
Correct |
166 ms |
301652 KB |
Output is correct |
55 |
Correct |
134 ms |
301608 KB |
Output is correct |
56 |
Correct |
129 ms |
301168 KB |
Output is correct |
57 |
Correct |
140 ms |
301004 KB |
Output is correct |
58 |
Correct |
113 ms |
296272 KB |
Output is correct |
59 |
Correct |
114 ms |
296272 KB |
Output is correct |
60 |
Correct |
115 ms |
296316 KB |
Output is correct |
61 |
Correct |
645 ms |
392280 KB |
Output is correct |
62 |
Correct |
1383 ms |
492328 KB |
Output is correct |
63 |
Correct |
1316 ms |
493156 KB |
Output is correct |
64 |
Correct |
1382 ms |
493268 KB |
Output is correct |
65 |
Correct |
246 ms |
338504 KB |
Output is correct |
66 |
Correct |
391 ms |
378196 KB |
Output is correct |
67 |
Correct |
436 ms |
381972 KB |
Output is correct |
68 |
Correct |
125 ms |
296016 KB |
Output is correct |
69 |
Correct |
119 ms |
296184 KB |
Output is correct |
70 |
Correct |
123 ms |
296552 KB |
Output is correct |
71 |
Correct |
127 ms |
296232 KB |
Output is correct |
72 |
Correct |
121 ms |
296064 KB |
Output is correct |
73 |
Correct |
1733 ms |
624664 KB |
Output is correct |
74 |
Correct |
1743 ms |
536216 KB |
Output is correct |
75 |
Correct |
1310 ms |
536544 KB |
Output is correct |
76 |
Correct |
1178 ms |
448036 KB |
Output is correct |
77 |
Correct |
1886 ms |
818548 KB |
Output is correct |
78 |
Correct |
1866 ms |
486556 KB |
Output is correct |
79 |
Correct |
1910 ms |
509912 KB |
Output is correct |
80 |
Correct |
2935 ms |
605584 KB |
Output is correct |
81 |
Correct |
1822 ms |
502176 KB |
Output is correct |
82 |
Correct |
2582 ms |
570324 KB |
Output is correct |
83 |
Correct |
3309 ms |
631408 KB |
Output is correct |
84 |
Correct |
1710 ms |
484264 KB |
Output is correct |
85 |
Correct |
2942 ms |
616628 KB |
Output is correct |
86 |
Correct |
2904 ms |
607264 KB |
Output is correct |
87 |
Correct |
1265 ms |
619460 KB |
Output is correct |
88 |
Correct |
1821 ms |
818368 KB |
Output is correct |
89 |
Correct |
1874 ms |
818468 KB |
Output is correct |
90 |
Correct |
1830 ms |
818736 KB |
Output is correct |