#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
using namespace std;
const int MM = 2505;
int n, m, ans;
int first[MM], last[MM], bit[MM];
stack<pair<int, int>> st;
map<int, int, greater<int>> hor[MM][MM], vert[MM][MM];
//stores either right or down endpoint, and "dp" val
void update(int i, int v){
for(; i < MM; i += i&-i)
bit[i] += v;
}
int query(int i){
int ret = 0;
for(; i; i -= i&-i)
ret += bit[i];
return ret;
}
void clear(){
while(!st.empty())
st.pop();
}
vector<pair<int, int>> vec;
long long count_rectangles(vector<vector<int>> a){
n = a.size(), m = a[0].size();
for(int i = 0; i < n; i++){
clear();
for(int j = 0; j < m; j++){
//remove duplicates
while(!st.empty() && st.top().first < a[i][j])
st.pop();
first[j] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second;
st.push({a[i][j], j});
}
clear();
for(int j = m-1; j >= 0; j--){
while(!st.empty() && st.top().first <= a[i][j])
st.pop();
last[j] = st.empty() ? -1 : st.top().second;
st.push({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]][last[j]] = 1;
}
}
for(int j = 0; j < m; j++){
clear();
for(int i = 0; i < n; i++){
//remove duplicates
while(!st.empty() && st.top().first < a[i][j])
st.pop();
first[i] = (st.empty() || st.top().first == a[i][j]) ? -1 : st.top().second;
st.push({a[i][j], i});
}
clear();
for(int i = n-1; i >= 0; i--){
while(!st.empty() && st.top().first <= a[i][j])
st.pop();
last[i] = st.empty() ? -1 : st.top().second;
st.push({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][last[i]] = 1;
}
}
for(int i = n-1; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
for(auto &x: hor[i][j])
if(hor[i+1][j].count(x.first))
x.second += hor[i+1][j][x.first];
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])
vec.push_back({x.first-j+1, x.second}); //adjust
sort(vec.begin(), vec.end(), [](auto &x, auto &y){
return x.second > y.second;
});
int l = 0;
for(auto &b: vert[i][j]){
int bf = b.first-i+1;
while(l < vec.size() && bf <= vec[l].second)
update(vec[l++].first, 1);
ans += query(b.second);
}
while(l)
update(vec[--l].first, -1);
vec.clear();
}
}
return ans;
}
/*
#ifndef ONLINE_JUDGE
int main(){
print(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
*/
/*
* in a row, for every point, get 1st left > and 1st right greater
* this will get all possible
*
* using mono stack
*
*
* sort row segments
* starting at point i, on row j
* for each (i, r), dp for how long can go down
*
* then do same for vertical
*
* when it works is when: vert_seg <= dp_vert[hor_seg] and hor_seg <= dp_hor[vert_seg]
*
* sort hor and vert by y reversed
* loop through vert with l ptr for hor
* while hor[l] >= y, push hor[l++].x into bit
* answer += query_greater_than_equals(vert[i].x)
*
* vertical <= NM
* horizontal <= NM
* time complexity vert * log(hor) = NM log(NM)
*/
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:120:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < vec.size() && bf <= vec[l].second)
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
589848 KB |
Output is correct |
2 |
Correct |
554 ms |
589956 KB |
Output is correct |
3 |
Correct |
529 ms |
589928 KB |
Output is correct |
4 |
Correct |
534 ms |
589916 KB |
Output is correct |
5 |
Correct |
537 ms |
589788 KB |
Output is correct |
6 |
Correct |
542 ms |
589952 KB |
Output is correct |
7 |
Correct |
536 ms |
589932 KB |
Output is correct |
8 |
Correct |
592 ms |
589916 KB |
Output is correct |
9 |
Correct |
537 ms |
589832 KB |
Output is correct |
10 |
Correct |
531 ms |
589796 KB |
Output is correct |
11 |
Correct |
533 ms |
589776 KB |
Output is correct |
12 |
Correct |
544 ms |
589832 KB |
Output is correct |
13 |
Correct |
563 ms |
589688 KB |
Output is correct |
14 |
Correct |
533 ms |
589768 KB |
Output is correct |
15 |
Correct |
551 ms |
589856 KB |
Output is correct |
16 |
Correct |
533 ms |
589816 KB |
Output is correct |
17 |
Correct |
528 ms |
589780 KB |
Output is correct |
18 |
Correct |
529 ms |
589748 KB |
Output is correct |
19 |
Correct |
584 ms |
590020 KB |
Output is correct |
20 |
Correct |
602 ms |
589728 KB |
Output is correct |
21 |
Correct |
537 ms |
589800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
589848 KB |
Output is correct |
2 |
Correct |
554 ms |
589956 KB |
Output is correct |
3 |
Correct |
529 ms |
589928 KB |
Output is correct |
4 |
Correct |
534 ms |
589916 KB |
Output is correct |
5 |
Correct |
537 ms |
589788 KB |
Output is correct |
6 |
Correct |
542 ms |
589952 KB |
Output is correct |
7 |
Correct |
536 ms |
589932 KB |
Output is correct |
8 |
Correct |
592 ms |
589916 KB |
Output is correct |
9 |
Correct |
537 ms |
589832 KB |
Output is correct |
10 |
Correct |
531 ms |
589796 KB |
Output is correct |
11 |
Correct |
533 ms |
589776 KB |
Output is correct |
12 |
Correct |
544 ms |
589832 KB |
Output is correct |
13 |
Correct |
563 ms |
589688 KB |
Output is correct |
14 |
Correct |
533 ms |
589768 KB |
Output is correct |
15 |
Correct |
551 ms |
589856 KB |
Output is correct |
16 |
Correct |
533 ms |
589816 KB |
Output is correct |
17 |
Correct |
614 ms |
590420 KB |
Output is correct |
18 |
Correct |
542 ms |
590520 KB |
Output is correct |
19 |
Correct |
585 ms |
590700 KB |
Output is correct |
20 |
Correct |
567 ms |
590044 KB |
Output is correct |
21 |
Correct |
538 ms |
590408 KB |
Output is correct |
22 |
Correct |
537 ms |
590396 KB |
Output is correct |
23 |
Correct |
537 ms |
590388 KB |
Output is correct |
24 |
Correct |
536 ms |
590012 KB |
Output is correct |
25 |
Correct |
528 ms |
589780 KB |
Output is correct |
26 |
Correct |
529 ms |
589748 KB |
Output is correct |
27 |
Correct |
584 ms |
590020 KB |
Output is correct |
28 |
Correct |
602 ms |
589728 KB |
Output is correct |
29 |
Correct |
537 ms |
589800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
589848 KB |
Output is correct |
2 |
Correct |
554 ms |
589956 KB |
Output is correct |
3 |
Correct |
529 ms |
589928 KB |
Output is correct |
4 |
Correct |
534 ms |
589916 KB |
Output is correct |
5 |
Correct |
537 ms |
589788 KB |
Output is correct |
6 |
Correct |
542 ms |
589952 KB |
Output is correct |
7 |
Correct |
536 ms |
589932 KB |
Output is correct |
8 |
Correct |
592 ms |
589916 KB |
Output is correct |
9 |
Correct |
537 ms |
589832 KB |
Output is correct |
10 |
Correct |
531 ms |
589796 KB |
Output is correct |
11 |
Correct |
533 ms |
589776 KB |
Output is correct |
12 |
Correct |
544 ms |
589832 KB |
Output is correct |
13 |
Correct |
563 ms |
589688 KB |
Output is correct |
14 |
Correct |
533 ms |
589768 KB |
Output is correct |
15 |
Correct |
551 ms |
589856 KB |
Output is correct |
16 |
Correct |
533 ms |
589816 KB |
Output is correct |
17 |
Correct |
614 ms |
590420 KB |
Output is correct |
18 |
Correct |
542 ms |
590520 KB |
Output is correct |
19 |
Correct |
585 ms |
590700 KB |
Output is correct |
20 |
Correct |
567 ms |
590044 KB |
Output is correct |
21 |
Correct |
538 ms |
590408 KB |
Output is correct |
22 |
Correct |
537 ms |
590396 KB |
Output is correct |
23 |
Correct |
537 ms |
590388 KB |
Output is correct |
24 |
Correct |
536 ms |
590012 KB |
Output is correct |
25 |
Correct |
559 ms |
593976 KB |
Output is correct |
26 |
Correct |
566 ms |
594052 KB |
Output is correct |
27 |
Correct |
579 ms |
594128 KB |
Output is correct |
28 |
Correct |
546 ms |
591588 KB |
Output is correct |
29 |
Correct |
555 ms |
593772 KB |
Output is correct |
30 |
Correct |
557 ms |
594044 KB |
Output is correct |
31 |
Correct |
594 ms |
593600 KB |
Output is correct |
32 |
Correct |
644 ms |
593768 KB |
Output is correct |
33 |
Correct |
528 ms |
589780 KB |
Output is correct |
34 |
Correct |
529 ms |
589748 KB |
Output is correct |
35 |
Correct |
584 ms |
590020 KB |
Output is correct |
36 |
Correct |
602 ms |
589728 KB |
Output is correct |
37 |
Correct |
537 ms |
589800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
589848 KB |
Output is correct |
2 |
Correct |
554 ms |
589956 KB |
Output is correct |
3 |
Correct |
529 ms |
589928 KB |
Output is correct |
4 |
Correct |
534 ms |
589916 KB |
Output is correct |
5 |
Correct |
537 ms |
589788 KB |
Output is correct |
6 |
Correct |
542 ms |
589952 KB |
Output is correct |
7 |
Correct |
536 ms |
589932 KB |
Output is correct |
8 |
Correct |
592 ms |
589916 KB |
Output is correct |
9 |
Correct |
537 ms |
589832 KB |
Output is correct |
10 |
Correct |
531 ms |
589796 KB |
Output is correct |
11 |
Correct |
533 ms |
589776 KB |
Output is correct |
12 |
Correct |
544 ms |
589832 KB |
Output is correct |
13 |
Correct |
563 ms |
589688 KB |
Output is correct |
14 |
Correct |
533 ms |
589768 KB |
Output is correct |
15 |
Correct |
551 ms |
589856 KB |
Output is correct |
16 |
Correct |
533 ms |
589816 KB |
Output is correct |
17 |
Correct |
614 ms |
590420 KB |
Output is correct |
18 |
Correct |
542 ms |
590520 KB |
Output is correct |
19 |
Correct |
585 ms |
590700 KB |
Output is correct |
20 |
Correct |
567 ms |
590044 KB |
Output is correct |
21 |
Correct |
538 ms |
590408 KB |
Output is correct |
22 |
Correct |
537 ms |
590396 KB |
Output is correct |
23 |
Correct |
537 ms |
590388 KB |
Output is correct |
24 |
Correct |
536 ms |
590012 KB |
Output is correct |
25 |
Correct |
559 ms |
593976 KB |
Output is correct |
26 |
Correct |
566 ms |
594052 KB |
Output is correct |
27 |
Correct |
579 ms |
594128 KB |
Output is correct |
28 |
Correct |
546 ms |
591588 KB |
Output is correct |
29 |
Correct |
555 ms |
593772 KB |
Output is correct |
30 |
Correct |
557 ms |
594044 KB |
Output is correct |
31 |
Correct |
594 ms |
593600 KB |
Output is correct |
32 |
Correct |
644 ms |
593768 KB |
Output is correct |
33 |
Correct |
707 ms |
617896 KB |
Output is correct |
34 |
Correct |
771 ms |
618044 KB |
Output is correct |
35 |
Correct |
731 ms |
618008 KB |
Output is correct |
36 |
Correct |
686 ms |
617848 KB |
Output is correct |
37 |
Correct |
823 ms |
640832 KB |
Output is correct |
38 |
Correct |
820 ms |
640968 KB |
Output is correct |
39 |
Correct |
793 ms |
640924 KB |
Output is correct |
40 |
Correct |
875 ms |
637688 KB |
Output is correct |
41 |
Correct |
800 ms |
606212 KB |
Output is correct |
42 |
Correct |
820 ms |
612544 KB |
Output is correct |
43 |
Correct |
900 ms |
639596 KB |
Output is correct |
44 |
Correct |
883 ms |
640188 KB |
Output is correct |
45 |
Correct |
727 ms |
615552 KB |
Output is correct |
46 |
Correct |
712 ms |
615416 KB |
Output is correct |
47 |
Correct |
1006 ms |
636432 KB |
Output is correct |
48 |
Correct |
852 ms |
636488 KB |
Output is correct |
49 |
Correct |
528 ms |
589780 KB |
Output is correct |
50 |
Correct |
529 ms |
589748 KB |
Output is correct |
51 |
Correct |
584 ms |
590020 KB |
Output is correct |
52 |
Correct |
602 ms |
589728 KB |
Output is correct |
53 |
Correct |
537 ms |
589800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
540 ms |
590376 KB |
Output is correct |
2 |
Correct |
565 ms |
590268 KB |
Output is correct |
3 |
Correct |
609 ms |
589964 KB |
Output is correct |
4 |
Correct |
575 ms |
589732 KB |
Output is correct |
5 |
Correct |
543 ms |
590328 KB |
Output is correct |
6 |
Correct |
560 ms |
590284 KB |
Output is correct |
7 |
Correct |
612 ms |
590428 KB |
Output is correct |
8 |
Correct |
583 ms |
590284 KB |
Output is correct |
9 |
Correct |
568 ms |
590420 KB |
Output is correct |
10 |
Correct |
543 ms |
589920 KB |
Output is correct |
11 |
Correct |
552 ms |
590084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
595 ms |
589888 KB |
Output is correct |
2 |
Correct |
1389 ms |
680912 KB |
Output is correct |
3 |
Correct |
2547 ms |
787156 KB |
Output is correct |
4 |
Correct |
2426 ms |
788084 KB |
Output is correct |
5 |
Correct |
2264 ms |
788192 KB |
Output is correct |
6 |
Correct |
763 ms |
615544 KB |
Output is correct |
7 |
Correct |
1043 ms |
638456 KB |
Output is correct |
8 |
Correct |
1070 ms |
641516 KB |
Output is correct |
9 |
Correct |
528 ms |
589780 KB |
Output is correct |
10 |
Correct |
529 ms |
589748 KB |
Output is correct |
11 |
Correct |
584 ms |
590020 KB |
Output is correct |
12 |
Correct |
602 ms |
589728 KB |
Output is correct |
13 |
Correct |
537 ms |
589800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
589848 KB |
Output is correct |
2 |
Correct |
554 ms |
589956 KB |
Output is correct |
3 |
Correct |
529 ms |
589928 KB |
Output is correct |
4 |
Correct |
534 ms |
589916 KB |
Output is correct |
5 |
Correct |
537 ms |
589788 KB |
Output is correct |
6 |
Correct |
542 ms |
589952 KB |
Output is correct |
7 |
Correct |
536 ms |
589932 KB |
Output is correct |
8 |
Correct |
592 ms |
589916 KB |
Output is correct |
9 |
Correct |
537 ms |
589832 KB |
Output is correct |
10 |
Correct |
531 ms |
589796 KB |
Output is correct |
11 |
Correct |
533 ms |
589776 KB |
Output is correct |
12 |
Correct |
544 ms |
589832 KB |
Output is correct |
13 |
Correct |
563 ms |
589688 KB |
Output is correct |
14 |
Correct |
533 ms |
589768 KB |
Output is correct |
15 |
Correct |
551 ms |
589856 KB |
Output is correct |
16 |
Correct |
533 ms |
589816 KB |
Output is correct |
17 |
Correct |
614 ms |
590420 KB |
Output is correct |
18 |
Correct |
542 ms |
590520 KB |
Output is correct |
19 |
Correct |
585 ms |
590700 KB |
Output is correct |
20 |
Correct |
567 ms |
590044 KB |
Output is correct |
21 |
Correct |
538 ms |
590408 KB |
Output is correct |
22 |
Correct |
537 ms |
590396 KB |
Output is correct |
23 |
Correct |
537 ms |
590388 KB |
Output is correct |
24 |
Correct |
536 ms |
590012 KB |
Output is correct |
25 |
Correct |
559 ms |
593976 KB |
Output is correct |
26 |
Correct |
566 ms |
594052 KB |
Output is correct |
27 |
Correct |
579 ms |
594128 KB |
Output is correct |
28 |
Correct |
546 ms |
591588 KB |
Output is correct |
29 |
Correct |
555 ms |
593772 KB |
Output is correct |
30 |
Correct |
557 ms |
594044 KB |
Output is correct |
31 |
Correct |
594 ms |
593600 KB |
Output is correct |
32 |
Correct |
644 ms |
593768 KB |
Output is correct |
33 |
Correct |
707 ms |
617896 KB |
Output is correct |
34 |
Correct |
771 ms |
618044 KB |
Output is correct |
35 |
Correct |
731 ms |
618008 KB |
Output is correct |
36 |
Correct |
686 ms |
617848 KB |
Output is correct |
37 |
Correct |
823 ms |
640832 KB |
Output is correct |
38 |
Correct |
820 ms |
640968 KB |
Output is correct |
39 |
Correct |
793 ms |
640924 KB |
Output is correct |
40 |
Correct |
875 ms |
637688 KB |
Output is correct |
41 |
Correct |
800 ms |
606212 KB |
Output is correct |
42 |
Correct |
820 ms |
612544 KB |
Output is correct |
43 |
Correct |
900 ms |
639596 KB |
Output is correct |
44 |
Correct |
883 ms |
640188 KB |
Output is correct |
45 |
Correct |
727 ms |
615552 KB |
Output is correct |
46 |
Correct |
712 ms |
615416 KB |
Output is correct |
47 |
Correct |
1006 ms |
636432 KB |
Output is correct |
48 |
Correct |
852 ms |
636488 KB |
Output is correct |
49 |
Correct |
540 ms |
590376 KB |
Output is correct |
50 |
Correct |
565 ms |
590268 KB |
Output is correct |
51 |
Correct |
609 ms |
589964 KB |
Output is correct |
52 |
Correct |
575 ms |
589732 KB |
Output is correct |
53 |
Correct |
543 ms |
590328 KB |
Output is correct |
54 |
Correct |
560 ms |
590284 KB |
Output is correct |
55 |
Correct |
612 ms |
590428 KB |
Output is correct |
56 |
Correct |
583 ms |
590284 KB |
Output is correct |
57 |
Correct |
568 ms |
590420 KB |
Output is correct |
58 |
Correct |
543 ms |
589920 KB |
Output is correct |
59 |
Correct |
552 ms |
590084 KB |
Output is correct |
60 |
Correct |
595 ms |
589888 KB |
Output is correct |
61 |
Correct |
1389 ms |
680912 KB |
Output is correct |
62 |
Correct |
2547 ms |
787156 KB |
Output is correct |
63 |
Correct |
2426 ms |
788084 KB |
Output is correct |
64 |
Correct |
2264 ms |
788192 KB |
Output is correct |
65 |
Correct |
763 ms |
615544 KB |
Output is correct |
66 |
Correct |
1043 ms |
638456 KB |
Output is correct |
67 |
Correct |
1070 ms |
641516 KB |
Output is correct |
68 |
Correct |
2563 ms |
932668 KB |
Output is correct |
69 |
Correct |
3227 ms |
932708 KB |
Output is correct |
70 |
Correct |
2143 ms |
933076 KB |
Output is correct |
71 |
Correct |
2673 ms |
932896 KB |
Output is correct |
72 |
Runtime error |
1828 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
73 |
Halted |
0 ms |
0 KB |
- |