#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
const int MM = 2502;
int n, m, ans, stl, vecl;
int first[MM], last[MM], bit[MM];
std::pair<int, int> st[MM], vec[MM];
std::vector<std::pair<int, int>> hor[MM][MM], vert[MM][MM];
inline void update(int i, int v){
for(; i < MM; i += i&-i)
bit[i] += v;
}
inline int query(int i){
int ret = 0;
for(; i; i -= i&-i)
ret += bit[i];
return ret;
}
long long count_rectangles(std::vector<std::vector<int>> a){
n = a.size(), m = a[0].size();
for(int i = 0; i < n; i++){
stl = 0;
for(int j = 0; j < m; j++){
//remove duplicates
while(stl && st[stl].first < a[i][j])
stl--;
first[j] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
st[++stl] = {a[i][j], j};
}
stl = 0;
for(int j = m-1; j >= 0; j--){
while(stl && st[stl].first <= a[i][j])
stl--;
last[j] = !stl ? -1 : st[stl].second;
st[++stl] = {a[i][j], j};
}
for(int j = 0; j < m; j++){
if(first[j] == -1 || last[j] == -1)
continue;
first[j]++, last[j]--;
hor[i][first[j]].push_back({last[j], 1});
}
}
for(int j = 0; j < m; j++){
stl = 0;
for(int i = 0; i < n; i++){
//remove duplicates
while(stl && st[stl].first < a[i][j])
stl--;
first[i] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
st[++stl] = {a[i][j], i};
}
stl = 0;
for(int i = n-1; i >= 0; i--){
while(stl && st[stl].first <= a[i][j])
stl--;
last[i] = !stl ? -1 : st[stl].second;
st[++stl] = {a[i][j], i};
}
for(int i = 0; i < n; i++){
if(first[i] == -1 || last[i] == -1)
continue;
first[i]++, last[i]--;
vert[first[i]][j].push_back({last[i], 1});
}
}
for(int i = n-1; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
//assert(std::is_sorted(hor[i][j].begin(), hor[i][j].end()));
//assert(std::is_sorted(vert[i][j].begin(), vert[i][j].end()));
int l = 0, r = 0;
while(l < vert[i][j].size() && r < vert[i][j+1].size()){
if(vert[i][j][l].first == vert[i][j+1][r].first){
vert[i][j][l].second = vert[i][j+1][r].second+1;
l++;
}
else if(vert[i][j][l].first > vert[i][j+1][r].first)
r++;
else
l++;
}
l = r = 0;
while(l < hor[i][j].size() && r < hor[i+1][j].size()){
if(hor[i][j][l].first == hor[i+1][j][r].first){
hor[i][j][l].second = hor[i+1][j][r].second+1;
l++;
}
else if(hor[i][j][l].first > hor[i+1][j][r].first)
r++;
else
l++;
}
/*
for(auto &x: vert[i][j])
if(vert[i][j+1].count(x.first))
x.second += vert[i][j+1][x.first];
for(auto &x: hor[i][j]){
if(hor[i+1][j].count(x.first))
x.second += hor[i+1][j][x.first];
vec[vecl++] = {x.first-j+1, x.second};
}
*/
for(int k = 0; k < hor[i][j].size(); k++)
vec[k] = hor[i][j][k];
vecl = hor[i][j].size();
sort(vec, vec+vecl, [](const std::pair<int, int> &x, const std::pair<int, int> &y){
return x.second > y.second;
});
l = 0;
for(int k = vert[i][j].size()-1; k >= 0; k--){
auto &b = vert[i][j][k];
while(l < vecl && b.first-i+1 <= vec[l].second){
update(vec[l++].first-j+1, 1);
}
ans += query(b.second);
}
while(l)
update(vec[--l].first-j+1, -1);
}
}
return ans;
}
#ifndef ONLINE_JUDGE
int notmain(){
printf("%lld\n", count_rectangles({{4, 8, 7, 5, 6},
{7, 4, 10, 3, 5},
{9, 7, 20, 14, 2},
{9, 14, 7, 3, 6},
{5, 7, 5, 2, 7},
{4, 5, 13, 5, 6}})
);
return 0;
}
#endif
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < vert[i][j].size() && r < vert[i][j+1].size()){
~~^~~~~~~~~~~~~~~~~~~
rect.cpp:88:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < vert[i][j].size() && r < vert[i][j+1].size()){
~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < hor[i][j].size() && r < hor[i+1][j].size()){
~~^~~~~~~~~~~~~~~~~~
rect.cpp:101:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < hor[i][j].size() && r < hor[i+1][j].size()){
~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:123:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < hor[i][j].size(); k++)
~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
294368 KB |
Output is correct |
2 |
Correct |
290 ms |
294424 KB |
Output is correct |
3 |
Correct |
298 ms |
294480 KB |
Output is correct |
4 |
Correct |
292 ms |
294520 KB |
Output is correct |
5 |
Correct |
289 ms |
294264 KB |
Output is correct |
6 |
Correct |
304 ms |
294308 KB |
Output is correct |
7 |
Correct |
289 ms |
294424 KB |
Output is correct |
8 |
Correct |
289 ms |
294468 KB |
Output is correct |
9 |
Correct |
286 ms |
294520 KB |
Output is correct |
10 |
Correct |
301 ms |
294540 KB |
Output is correct |
11 |
Correct |
289 ms |
294392 KB |
Output is correct |
12 |
Correct |
286 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
14 |
Correct |
287 ms |
294408 KB |
Output is correct |
15 |
Correct |
330 ms |
294268 KB |
Output is correct |
16 |
Correct |
290 ms |
294392 KB |
Output is correct |
17 |
Correct |
300 ms |
294264 KB |
Output is correct |
18 |
Correct |
293 ms |
294380 KB |
Output is correct |
19 |
Correct |
310 ms |
294308 KB |
Output is correct |
20 |
Correct |
288 ms |
294392 KB |
Output is correct |
21 |
Correct |
287 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
294368 KB |
Output is correct |
2 |
Correct |
290 ms |
294424 KB |
Output is correct |
3 |
Correct |
298 ms |
294480 KB |
Output is correct |
4 |
Correct |
292 ms |
294520 KB |
Output is correct |
5 |
Correct |
289 ms |
294264 KB |
Output is correct |
6 |
Correct |
304 ms |
294308 KB |
Output is correct |
7 |
Correct |
289 ms |
294424 KB |
Output is correct |
8 |
Correct |
289 ms |
294468 KB |
Output is correct |
9 |
Correct |
286 ms |
294520 KB |
Output is correct |
10 |
Correct |
301 ms |
294540 KB |
Output is correct |
11 |
Correct |
289 ms |
294392 KB |
Output is correct |
12 |
Correct |
286 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
14 |
Correct |
287 ms |
294408 KB |
Output is correct |
15 |
Correct |
330 ms |
294268 KB |
Output is correct |
16 |
Correct |
290 ms |
294392 KB |
Output is correct |
17 |
Correct |
291 ms |
294888 KB |
Output is correct |
18 |
Correct |
290 ms |
294776 KB |
Output is correct |
19 |
Correct |
292 ms |
294904 KB |
Output is correct |
20 |
Correct |
288 ms |
294588 KB |
Output is correct |
21 |
Correct |
292 ms |
294672 KB |
Output is correct |
22 |
Correct |
288 ms |
294692 KB |
Output is correct |
23 |
Correct |
289 ms |
294692 KB |
Output is correct |
24 |
Correct |
287 ms |
294520 KB |
Output is correct |
25 |
Correct |
300 ms |
294264 KB |
Output is correct |
26 |
Correct |
293 ms |
294380 KB |
Output is correct |
27 |
Correct |
310 ms |
294308 KB |
Output is correct |
28 |
Correct |
288 ms |
294392 KB |
Output is correct |
29 |
Correct |
287 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
294368 KB |
Output is correct |
2 |
Correct |
290 ms |
294424 KB |
Output is correct |
3 |
Correct |
298 ms |
294480 KB |
Output is correct |
4 |
Correct |
292 ms |
294520 KB |
Output is correct |
5 |
Correct |
289 ms |
294264 KB |
Output is correct |
6 |
Correct |
304 ms |
294308 KB |
Output is correct |
7 |
Correct |
289 ms |
294424 KB |
Output is correct |
8 |
Correct |
289 ms |
294468 KB |
Output is correct |
9 |
Correct |
286 ms |
294520 KB |
Output is correct |
10 |
Correct |
301 ms |
294540 KB |
Output is correct |
11 |
Correct |
289 ms |
294392 KB |
Output is correct |
12 |
Correct |
286 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
14 |
Correct |
287 ms |
294408 KB |
Output is correct |
15 |
Correct |
330 ms |
294268 KB |
Output is correct |
16 |
Correct |
290 ms |
294392 KB |
Output is correct |
17 |
Correct |
291 ms |
294888 KB |
Output is correct |
18 |
Correct |
290 ms |
294776 KB |
Output is correct |
19 |
Correct |
292 ms |
294904 KB |
Output is correct |
20 |
Correct |
288 ms |
294588 KB |
Output is correct |
21 |
Correct |
292 ms |
294672 KB |
Output is correct |
22 |
Correct |
288 ms |
294692 KB |
Output is correct |
23 |
Correct |
289 ms |
294692 KB |
Output is correct |
24 |
Correct |
287 ms |
294520 KB |
Output is correct |
25 |
Correct |
325 ms |
297288 KB |
Output is correct |
26 |
Correct |
301 ms |
297440 KB |
Output is correct |
27 |
Correct |
301 ms |
297496 KB |
Output is correct |
28 |
Correct |
295 ms |
295612 KB |
Output is correct |
29 |
Correct |
302 ms |
296284 KB |
Output is correct |
30 |
Correct |
304 ms |
296404 KB |
Output is correct |
31 |
Correct |
308 ms |
296312 KB |
Output is correct |
32 |
Correct |
346 ms |
296312 KB |
Output is correct |
33 |
Correct |
300 ms |
294264 KB |
Output is correct |
34 |
Correct |
293 ms |
294380 KB |
Output is correct |
35 |
Correct |
310 ms |
294308 KB |
Output is correct |
36 |
Correct |
288 ms |
294392 KB |
Output is correct |
37 |
Correct |
287 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
294368 KB |
Output is correct |
2 |
Correct |
290 ms |
294424 KB |
Output is correct |
3 |
Correct |
298 ms |
294480 KB |
Output is correct |
4 |
Correct |
292 ms |
294520 KB |
Output is correct |
5 |
Correct |
289 ms |
294264 KB |
Output is correct |
6 |
Correct |
304 ms |
294308 KB |
Output is correct |
7 |
Correct |
289 ms |
294424 KB |
Output is correct |
8 |
Correct |
289 ms |
294468 KB |
Output is correct |
9 |
Correct |
286 ms |
294520 KB |
Output is correct |
10 |
Correct |
301 ms |
294540 KB |
Output is correct |
11 |
Correct |
289 ms |
294392 KB |
Output is correct |
12 |
Correct |
286 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
14 |
Correct |
287 ms |
294408 KB |
Output is correct |
15 |
Correct |
330 ms |
294268 KB |
Output is correct |
16 |
Correct |
290 ms |
294392 KB |
Output is correct |
17 |
Correct |
291 ms |
294888 KB |
Output is correct |
18 |
Correct |
290 ms |
294776 KB |
Output is correct |
19 |
Correct |
292 ms |
294904 KB |
Output is correct |
20 |
Correct |
288 ms |
294588 KB |
Output is correct |
21 |
Correct |
292 ms |
294672 KB |
Output is correct |
22 |
Correct |
288 ms |
294692 KB |
Output is correct |
23 |
Correct |
289 ms |
294692 KB |
Output is correct |
24 |
Correct |
287 ms |
294520 KB |
Output is correct |
25 |
Correct |
325 ms |
297288 KB |
Output is correct |
26 |
Correct |
301 ms |
297440 KB |
Output is correct |
27 |
Correct |
301 ms |
297496 KB |
Output is correct |
28 |
Correct |
295 ms |
295612 KB |
Output is correct |
29 |
Correct |
302 ms |
296284 KB |
Output is correct |
30 |
Correct |
304 ms |
296404 KB |
Output is correct |
31 |
Correct |
308 ms |
296312 KB |
Output is correct |
32 |
Correct |
346 ms |
296312 KB |
Output is correct |
33 |
Correct |
411 ms |
314916 KB |
Output is correct |
34 |
Correct |
416 ms |
310292 KB |
Output is correct |
35 |
Correct |
351 ms |
310416 KB |
Output is correct |
36 |
Correct |
357 ms |
305664 KB |
Output is correct |
37 |
Correct |
463 ms |
330612 KB |
Output is correct |
38 |
Correct |
460 ms |
330348 KB |
Output is correct |
39 |
Correct |
461 ms |
330488 KB |
Output is correct |
40 |
Correct |
480 ms |
328280 KB |
Output is correct |
41 |
Correct |
401 ms |
306920 KB |
Output is correct |
42 |
Correct |
433 ms |
309504 KB |
Output is correct |
43 |
Correct |
472 ms |
317260 KB |
Output is correct |
44 |
Correct |
485 ms |
318004 KB |
Output is correct |
45 |
Correct |
381 ms |
306296 KB |
Output is correct |
46 |
Correct |
439 ms |
306140 KB |
Output is correct |
47 |
Correct |
502 ms |
316124 KB |
Output is correct |
48 |
Correct |
474 ms |
316536 KB |
Output is correct |
49 |
Correct |
300 ms |
294264 KB |
Output is correct |
50 |
Correct |
293 ms |
294380 KB |
Output is correct |
51 |
Correct |
310 ms |
294308 KB |
Output is correct |
52 |
Correct |
288 ms |
294392 KB |
Output is correct |
53 |
Correct |
287 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
288 ms |
295032 KB |
Output is correct |
2 |
Correct |
289 ms |
294776 KB |
Output is correct |
3 |
Correct |
286 ms |
294520 KB |
Output is correct |
4 |
Correct |
289 ms |
294396 KB |
Output is correct |
5 |
Correct |
296 ms |
294636 KB |
Output is correct |
6 |
Correct |
308 ms |
294744 KB |
Output is correct |
7 |
Correct |
288 ms |
294648 KB |
Output is correct |
8 |
Correct |
299 ms |
294664 KB |
Output is correct |
9 |
Correct |
289 ms |
294648 KB |
Output is correct |
10 |
Correct |
302 ms |
294508 KB |
Output is correct |
11 |
Correct |
288 ms |
294520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
311 ms |
294416 KB |
Output is correct |
2 |
Correct |
917 ms |
363008 KB |
Output is correct |
3 |
Correct |
1689 ms |
443052 KB |
Output is correct |
4 |
Correct |
1604 ms |
443740 KB |
Output is correct |
5 |
Correct |
1624 ms |
443820 KB |
Output is correct |
6 |
Correct |
428 ms |
320248 KB |
Output is correct |
7 |
Correct |
592 ms |
343092 KB |
Output is correct |
8 |
Correct |
606 ms |
346228 KB |
Output is correct |
9 |
Correct |
300 ms |
294264 KB |
Output is correct |
10 |
Correct |
293 ms |
294380 KB |
Output is correct |
11 |
Correct |
310 ms |
294308 KB |
Output is correct |
12 |
Correct |
288 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
294368 KB |
Output is correct |
2 |
Correct |
290 ms |
294424 KB |
Output is correct |
3 |
Correct |
298 ms |
294480 KB |
Output is correct |
4 |
Correct |
292 ms |
294520 KB |
Output is correct |
5 |
Correct |
289 ms |
294264 KB |
Output is correct |
6 |
Correct |
304 ms |
294308 KB |
Output is correct |
7 |
Correct |
289 ms |
294424 KB |
Output is correct |
8 |
Correct |
289 ms |
294468 KB |
Output is correct |
9 |
Correct |
286 ms |
294520 KB |
Output is correct |
10 |
Correct |
301 ms |
294540 KB |
Output is correct |
11 |
Correct |
289 ms |
294392 KB |
Output is correct |
12 |
Correct |
286 ms |
294392 KB |
Output is correct |
13 |
Correct |
287 ms |
294392 KB |
Output is correct |
14 |
Correct |
287 ms |
294408 KB |
Output is correct |
15 |
Correct |
330 ms |
294268 KB |
Output is correct |
16 |
Correct |
290 ms |
294392 KB |
Output is correct |
17 |
Correct |
291 ms |
294888 KB |
Output is correct |
18 |
Correct |
290 ms |
294776 KB |
Output is correct |
19 |
Correct |
292 ms |
294904 KB |
Output is correct |
20 |
Correct |
288 ms |
294588 KB |
Output is correct |
21 |
Correct |
292 ms |
294672 KB |
Output is correct |
22 |
Correct |
288 ms |
294692 KB |
Output is correct |
23 |
Correct |
289 ms |
294692 KB |
Output is correct |
24 |
Correct |
287 ms |
294520 KB |
Output is correct |
25 |
Correct |
325 ms |
297288 KB |
Output is correct |
26 |
Correct |
301 ms |
297440 KB |
Output is correct |
27 |
Correct |
301 ms |
297496 KB |
Output is correct |
28 |
Correct |
295 ms |
295612 KB |
Output is correct |
29 |
Correct |
302 ms |
296284 KB |
Output is correct |
30 |
Correct |
304 ms |
296404 KB |
Output is correct |
31 |
Correct |
308 ms |
296312 KB |
Output is correct |
32 |
Correct |
346 ms |
296312 KB |
Output is correct |
33 |
Correct |
411 ms |
314916 KB |
Output is correct |
34 |
Correct |
416 ms |
310292 KB |
Output is correct |
35 |
Correct |
351 ms |
310416 KB |
Output is correct |
36 |
Correct |
357 ms |
305664 KB |
Output is correct |
37 |
Correct |
463 ms |
330612 KB |
Output is correct |
38 |
Correct |
460 ms |
330348 KB |
Output is correct |
39 |
Correct |
461 ms |
330488 KB |
Output is correct |
40 |
Correct |
480 ms |
328280 KB |
Output is correct |
41 |
Correct |
401 ms |
306920 KB |
Output is correct |
42 |
Correct |
433 ms |
309504 KB |
Output is correct |
43 |
Correct |
472 ms |
317260 KB |
Output is correct |
44 |
Correct |
485 ms |
318004 KB |
Output is correct |
45 |
Correct |
381 ms |
306296 KB |
Output is correct |
46 |
Correct |
439 ms |
306140 KB |
Output is correct |
47 |
Correct |
502 ms |
316124 KB |
Output is correct |
48 |
Correct |
474 ms |
316536 KB |
Output is correct |
49 |
Correct |
288 ms |
295032 KB |
Output is correct |
50 |
Correct |
289 ms |
294776 KB |
Output is correct |
51 |
Correct |
286 ms |
294520 KB |
Output is correct |
52 |
Correct |
289 ms |
294396 KB |
Output is correct |
53 |
Correct |
296 ms |
294636 KB |
Output is correct |
54 |
Correct |
308 ms |
294744 KB |
Output is correct |
55 |
Correct |
288 ms |
294648 KB |
Output is correct |
56 |
Correct |
299 ms |
294664 KB |
Output is correct |
57 |
Correct |
289 ms |
294648 KB |
Output is correct |
58 |
Correct |
302 ms |
294508 KB |
Output is correct |
59 |
Correct |
288 ms |
294520 KB |
Output is correct |
60 |
Correct |
311 ms |
294416 KB |
Output is correct |
61 |
Correct |
917 ms |
363008 KB |
Output is correct |
62 |
Correct |
1689 ms |
443052 KB |
Output is correct |
63 |
Correct |
1604 ms |
443740 KB |
Output is correct |
64 |
Correct |
1624 ms |
443820 KB |
Output is correct |
65 |
Correct |
428 ms |
320248 KB |
Output is correct |
66 |
Correct |
592 ms |
343092 KB |
Output is correct |
67 |
Correct |
606 ms |
346228 KB |
Output is correct |
68 |
Correct |
1721 ms |
540120 KB |
Output is correct |
69 |
Correct |
2066 ms |
473248 KB |
Output is correct |
70 |
Correct |
1072 ms |
473232 KB |
Output is correct |
71 |
Correct |
1211 ms |
406216 KB |
Output is correct |
72 |
Correct |
3280 ms |
735528 KB |
Output is correct |
73 |
Correct |
2013 ms |
472372 KB |
Output is correct |
74 |
Correct |
2023 ms |
472952 KB |
Output is correct |
75 |
Correct |
3101 ms |
574984 KB |
Output is correct |
76 |
Correct |
1915 ms |
464248 KB |
Output is correct |
77 |
Correct |
2500 ms |
521184 KB |
Output is correct |
78 |
Correct |
3308 ms |
577708 KB |
Output is correct |
79 |
Correct |
1877 ms |
453404 KB |
Output is correct |
80 |
Correct |
2993 ms |
563512 KB |
Output is correct |
81 |
Correct |
2901 ms |
553308 KB |
Output is correct |
82 |
Correct |
1924 ms |
559104 KB |
Output is correct |
83 |
Correct |
3240 ms |
735320 KB |
Output is correct |
84 |
Correct |
3217 ms |
735544 KB |
Output is correct |
85 |
Correct |
3376 ms |
737556 KB |
Output is correct |
86 |
Correct |
300 ms |
294264 KB |
Output is correct |
87 |
Correct |
293 ms |
294380 KB |
Output is correct |
88 |
Correct |
310 ms |
294308 KB |
Output is correct |
89 |
Correct |
288 ms |
294392 KB |
Output is correct |
90 |
Correct |
287 ms |
294392 KB |
Output is correct |