#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3005;
ll n, m, ans;
stack<int> st[NMAX];
pair<int, int> p[NMAX][NMAX];
ll count_rectangles(vector<vector<int>> a) {
n = a.size(); m = a[0].size();
for(int i = 0; i < m; i++){
st[i].emplace(0);
for(int j = 0; j < m; j++) p[i][j] = {-2, -2};
}
for(int i = 0; i + 1 < n; i++){
stack<pair<int, vector<int>>> s;
for(int j = 0; j < m; j++){
vector<int> cur;
int init = 0;
auto merge = [&](vector<int> & v){
if(!init) init = 1, cur = v;
else{
vector<int> tmp;
int j = 0;
for(int i = 0; i < cur.size(); i++){
while(j < v.size() && v[j] < cur[i]) j++;
if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]);
}
swap(cur, tmp);
}
};
while(s.size() && a[i][s.top().first] <= a[i][j]){
auto[x, v] = s.top(); s.pop();
merge(v);
if(s.size() && a[i][x] < a[i][j]){
int l = s.top().first;
if(p[l + 1][j - 1].second != i - 1) p[l + 1][j - 1].first = i;
p[l + 1][j - 1].second = i;
int up = p[l + 1][j - 1].first;
ans += cur.end() - lower_bound(all(cur), up);
}
}
vector<int> v;
while(st[j].size() && a[st[j].top()][j] <= a[i + 1][j]){
int y = st[j].top(); st[j].pop();
if(st[j].size() && a[y][j] < a[i + 1][j]) v.emplace_back(st[j].top() + 1);
}
st[j].emplace(i + 1);
reverse(all(v));
merge(v);
s.emplace(j, cur);
}
}
return ans;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m));
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> v[i][j];
cout << count_rectangles(v);
return 0;
}
*/
Compilation message
rect.cpp: In lambda function:
rect.cpp:30:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i = 0; i < cur.size(); i++){
| ~~^~~~~~~~~~~~
rect.cpp:31:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while(j < v.size() && v[j] < cur[i]) j++;
| ~~^~~~~~~~~~
rect.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]);
| ~~^~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | auto[x, v] = s.top(); s.pop();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2388 KB |
Output is correct |
3 |
Correct |
1 ms |
2388 KB |
Output is correct |
4 |
Correct |
1 ms |
2388 KB |
Output is correct |
5 |
Correct |
1 ms |
2388 KB |
Output is correct |
6 |
Correct |
1 ms |
2388 KB |
Output is correct |
7 |
Correct |
2 ms |
2388 KB |
Output is correct |
8 |
Correct |
2 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
1 ms |
2456 KB |
Output is correct |
11 |
Correct |
1 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
2388 KB |
Output is correct |
13 |
Correct |
1 ms |
2260 KB |
Output is correct |
14 |
Correct |
1 ms |
2260 KB |
Output is correct |
15 |
Correct |
1 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
2260 KB |
Output is correct |
17 |
Correct |
2 ms |
2260 KB |
Output is correct |
18 |
Correct |
1 ms |
2328 KB |
Output is correct |
19 |
Correct |
1 ms |
2452 KB |
Output is correct |
20 |
Correct |
1 ms |
2332 KB |
Output is correct |
21 |
Correct |
1 ms |
2260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2388 KB |
Output is correct |
3 |
Correct |
1 ms |
2388 KB |
Output is correct |
4 |
Correct |
1 ms |
2388 KB |
Output is correct |
5 |
Correct |
1 ms |
2388 KB |
Output is correct |
6 |
Correct |
1 ms |
2388 KB |
Output is correct |
7 |
Correct |
2 ms |
2388 KB |
Output is correct |
8 |
Correct |
2 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
1 ms |
2456 KB |
Output is correct |
11 |
Correct |
1 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
2388 KB |
Output is correct |
13 |
Correct |
1 ms |
2260 KB |
Output is correct |
14 |
Correct |
1 ms |
2260 KB |
Output is correct |
15 |
Correct |
1 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
2260 KB |
Output is correct |
17 |
Correct |
2 ms |
2260 KB |
Output is correct |
18 |
Correct |
1 ms |
2328 KB |
Output is correct |
19 |
Correct |
1 ms |
2452 KB |
Output is correct |
20 |
Correct |
1 ms |
2332 KB |
Output is correct |
21 |
Correct |
1 ms |
2260 KB |
Output is correct |
22 |
Correct |
2 ms |
2772 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2772 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
2 ms |
2724 KB |
Output is correct |
27 |
Correct |
2 ms |
2900 KB |
Output is correct |
28 |
Correct |
2 ms |
2772 KB |
Output is correct |
29 |
Correct |
2 ms |
2516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2388 KB |
Output is correct |
3 |
Correct |
1 ms |
2388 KB |
Output is correct |
4 |
Correct |
1 ms |
2388 KB |
Output is correct |
5 |
Correct |
1 ms |
2388 KB |
Output is correct |
6 |
Correct |
1 ms |
2388 KB |
Output is correct |
7 |
Correct |
2 ms |
2388 KB |
Output is correct |
8 |
Correct |
2 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
1 ms |
2456 KB |
Output is correct |
11 |
Correct |
1 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
2388 KB |
Output is correct |
13 |
Correct |
1 ms |
2260 KB |
Output is correct |
14 |
Correct |
1 ms |
2260 KB |
Output is correct |
15 |
Correct |
1 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
2260 KB |
Output is correct |
17 |
Correct |
2 ms |
2772 KB |
Output is correct |
18 |
Correct |
2 ms |
2772 KB |
Output is correct |
19 |
Correct |
2 ms |
2772 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2724 KB |
Output is correct |
22 |
Correct |
2 ms |
2900 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2516 KB |
Output is correct |
25 |
Correct |
2 ms |
2260 KB |
Output is correct |
26 |
Correct |
1 ms |
2328 KB |
Output is correct |
27 |
Correct |
1 ms |
2452 KB |
Output is correct |
28 |
Correct |
1 ms |
2332 KB |
Output is correct |
29 |
Correct |
1 ms |
2260 KB |
Output is correct |
30 |
Correct |
4 ms |
4128 KB |
Output is correct |
31 |
Correct |
4 ms |
4052 KB |
Output is correct |
32 |
Correct |
5 ms |
4180 KB |
Output is correct |
33 |
Correct |
5 ms |
3796 KB |
Output is correct |
34 |
Correct |
7 ms |
3908 KB |
Output is correct |
35 |
Correct |
7 ms |
4120 KB |
Output is correct |
36 |
Correct |
7 ms |
4004 KB |
Output is correct |
37 |
Correct |
7 ms |
3984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2388 KB |
Output is correct |
3 |
Correct |
1 ms |
2388 KB |
Output is correct |
4 |
Correct |
1 ms |
2388 KB |
Output is correct |
5 |
Correct |
1 ms |
2388 KB |
Output is correct |
6 |
Correct |
1 ms |
2388 KB |
Output is correct |
7 |
Correct |
2 ms |
2388 KB |
Output is correct |
8 |
Correct |
2 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
1 ms |
2456 KB |
Output is correct |
11 |
Correct |
1 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
2388 KB |
Output is correct |
13 |
Correct |
1 ms |
2260 KB |
Output is correct |
14 |
Correct |
1 ms |
2260 KB |
Output is correct |
15 |
Correct |
1 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
2260 KB |
Output is correct |
17 |
Correct |
2 ms |
2772 KB |
Output is correct |
18 |
Correct |
2 ms |
2772 KB |
Output is correct |
19 |
Correct |
2 ms |
2772 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2724 KB |
Output is correct |
22 |
Correct |
2 ms |
2900 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2516 KB |
Output is correct |
25 |
Correct |
4 ms |
4128 KB |
Output is correct |
26 |
Correct |
4 ms |
4052 KB |
Output is correct |
27 |
Correct |
5 ms |
4180 KB |
Output is correct |
28 |
Correct |
5 ms |
3796 KB |
Output is correct |
29 |
Correct |
7 ms |
3908 KB |
Output is correct |
30 |
Correct |
7 ms |
4120 KB |
Output is correct |
31 |
Correct |
7 ms |
4004 KB |
Output is correct |
32 |
Correct |
7 ms |
3984 KB |
Output is correct |
33 |
Correct |
2 ms |
2260 KB |
Output is correct |
34 |
Correct |
1 ms |
2328 KB |
Output is correct |
35 |
Correct |
1 ms |
2452 KB |
Output is correct |
36 |
Correct |
1 ms |
2332 KB |
Output is correct |
37 |
Correct |
1 ms |
2260 KB |
Output is correct |
38 |
Correct |
32 ms |
16540 KB |
Output is correct |
39 |
Correct |
31 ms |
16544 KB |
Output is correct |
40 |
Correct |
41 ms |
16908 KB |
Output is correct |
41 |
Correct |
43 ms |
16792 KB |
Output is correct |
42 |
Correct |
37 ms |
18504 KB |
Output is correct |
43 |
Correct |
38 ms |
18456 KB |
Output is correct |
44 |
Correct |
39 ms |
18764 KB |
Output is correct |
45 |
Correct |
39 ms |
18340 KB |
Output is correct |
46 |
Correct |
33 ms |
13780 KB |
Output is correct |
47 |
Correct |
41 ms |
13800 KB |
Output is correct |
48 |
Correct |
69 ms |
14636 KB |
Output is correct |
49 |
Correct |
71 ms |
16548 KB |
Output is correct |
50 |
Correct |
36 ms |
8484 KB |
Output is correct |
51 |
Correct |
37 ms |
12756 KB |
Output is correct |
52 |
Correct |
67 ms |
15612 KB |
Output is correct |
53 |
Correct |
70 ms |
16580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
61240 KB |
Output is correct |
2 |
Correct |
26 ms |
46292 KB |
Output is correct |
3 |
Correct |
29 ms |
61104 KB |
Output is correct |
4 |
Correct |
1 ms |
2260 KB |
Output is correct |
5 |
Correct |
28 ms |
61180 KB |
Output is correct |
6 |
Correct |
29 ms |
61176 KB |
Output is correct |
7 |
Correct |
30 ms |
61068 KB |
Output is correct |
8 |
Correct |
29 ms |
61084 KB |
Output is correct |
9 |
Correct |
29 ms |
61156 KB |
Output is correct |
10 |
Correct |
32 ms |
61196 KB |
Output is correct |
11 |
Correct |
29 ms |
61072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
1 ms |
2328 KB |
Output is correct |
3 |
Correct |
1 ms |
2452 KB |
Output is correct |
4 |
Correct |
1 ms |
2332 KB |
Output is correct |
5 |
Correct |
1 ms |
2260 KB |
Output is correct |
6 |
Correct |
1 ms |
2260 KB |
Output is correct |
7 |
Correct |
218 ms |
76268 KB |
Output is correct |
8 |
Correct |
475 ms |
122120 KB |
Output is correct |
9 |
Correct |
457 ms |
122344 KB |
Output is correct |
10 |
Correct |
454 ms |
122516 KB |
Output is correct |
11 |
Correct |
124 ms |
91392 KB |
Output is correct |
12 |
Correct |
223 ms |
112252 KB |
Output is correct |
13 |
Correct |
235 ms |
122316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2388 KB |
Output is correct |
3 |
Correct |
1 ms |
2388 KB |
Output is correct |
4 |
Correct |
1 ms |
2388 KB |
Output is correct |
5 |
Correct |
1 ms |
2388 KB |
Output is correct |
6 |
Correct |
1 ms |
2388 KB |
Output is correct |
7 |
Correct |
2 ms |
2388 KB |
Output is correct |
8 |
Correct |
2 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
1 ms |
2456 KB |
Output is correct |
11 |
Correct |
1 ms |
2388 KB |
Output is correct |
12 |
Correct |
1 ms |
2388 KB |
Output is correct |
13 |
Correct |
1 ms |
2260 KB |
Output is correct |
14 |
Correct |
1 ms |
2260 KB |
Output is correct |
15 |
Correct |
1 ms |
2260 KB |
Output is correct |
16 |
Correct |
1 ms |
2260 KB |
Output is correct |
17 |
Correct |
2 ms |
2772 KB |
Output is correct |
18 |
Correct |
2 ms |
2772 KB |
Output is correct |
19 |
Correct |
2 ms |
2772 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2724 KB |
Output is correct |
22 |
Correct |
2 ms |
2900 KB |
Output is correct |
23 |
Correct |
2 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2516 KB |
Output is correct |
25 |
Correct |
4 ms |
4128 KB |
Output is correct |
26 |
Correct |
4 ms |
4052 KB |
Output is correct |
27 |
Correct |
5 ms |
4180 KB |
Output is correct |
28 |
Correct |
5 ms |
3796 KB |
Output is correct |
29 |
Correct |
7 ms |
3908 KB |
Output is correct |
30 |
Correct |
7 ms |
4120 KB |
Output is correct |
31 |
Correct |
7 ms |
4004 KB |
Output is correct |
32 |
Correct |
7 ms |
3984 KB |
Output is correct |
33 |
Correct |
32 ms |
16540 KB |
Output is correct |
34 |
Correct |
31 ms |
16544 KB |
Output is correct |
35 |
Correct |
41 ms |
16908 KB |
Output is correct |
36 |
Correct |
43 ms |
16792 KB |
Output is correct |
37 |
Correct |
37 ms |
18504 KB |
Output is correct |
38 |
Correct |
38 ms |
18456 KB |
Output is correct |
39 |
Correct |
39 ms |
18764 KB |
Output is correct |
40 |
Correct |
39 ms |
18340 KB |
Output is correct |
41 |
Correct |
33 ms |
13780 KB |
Output is correct |
42 |
Correct |
41 ms |
13800 KB |
Output is correct |
43 |
Correct |
69 ms |
14636 KB |
Output is correct |
44 |
Correct |
71 ms |
16548 KB |
Output is correct |
45 |
Correct |
36 ms |
8484 KB |
Output is correct |
46 |
Correct |
37 ms |
12756 KB |
Output is correct |
47 |
Correct |
67 ms |
15612 KB |
Output is correct |
48 |
Correct |
70 ms |
16580 KB |
Output is correct |
49 |
Correct |
29 ms |
61240 KB |
Output is correct |
50 |
Correct |
26 ms |
46292 KB |
Output is correct |
51 |
Correct |
29 ms |
61104 KB |
Output is correct |
52 |
Correct |
1 ms |
2260 KB |
Output is correct |
53 |
Correct |
28 ms |
61180 KB |
Output is correct |
54 |
Correct |
29 ms |
61176 KB |
Output is correct |
55 |
Correct |
30 ms |
61068 KB |
Output is correct |
56 |
Correct |
29 ms |
61084 KB |
Output is correct |
57 |
Correct |
29 ms |
61156 KB |
Output is correct |
58 |
Correct |
32 ms |
61196 KB |
Output is correct |
59 |
Correct |
29 ms |
61072 KB |
Output is correct |
60 |
Correct |
1 ms |
2260 KB |
Output is correct |
61 |
Correct |
218 ms |
76268 KB |
Output is correct |
62 |
Correct |
475 ms |
122120 KB |
Output is correct |
63 |
Correct |
457 ms |
122344 KB |
Output is correct |
64 |
Correct |
454 ms |
122516 KB |
Output is correct |
65 |
Correct |
124 ms |
91392 KB |
Output is correct |
66 |
Correct |
223 ms |
112252 KB |
Output is correct |
67 |
Correct |
235 ms |
122316 KB |
Output is correct |
68 |
Correct |
2 ms |
2260 KB |
Output is correct |
69 |
Correct |
1 ms |
2328 KB |
Output is correct |
70 |
Correct |
1 ms |
2452 KB |
Output is correct |
71 |
Correct |
1 ms |
2332 KB |
Output is correct |
72 |
Correct |
1 ms |
2260 KB |
Output is correct |
73 |
Correct |
538 ms |
163676 KB |
Output is correct |
74 |
Correct |
446 ms |
163696 KB |
Output is correct |
75 |
Correct |
670 ms |
169480 KB |
Output is correct |
76 |
Correct |
640 ms |
169644 KB |
Output is correct |
77 |
Correct |
673 ms |
186956 KB |
Output is correct |
78 |
Correct |
545 ms |
104228 KB |
Output is correct |
79 |
Correct |
587 ms |
81216 KB |
Output is correct |
80 |
Correct |
944 ms |
132968 KB |
Output is correct |
81 |
Correct |
657 ms |
119300 KB |
Output is correct |
82 |
Correct |
841 ms |
119256 KB |
Output is correct |
83 |
Correct |
1014 ms |
158100 KB |
Output is correct |
84 |
Correct |
567 ms |
112072 KB |
Output is correct |
85 |
Correct |
948 ms |
158240 KB |
Output is correct |
86 |
Correct |
931 ms |
155576 KB |
Output is correct |
87 |
Correct |
325 ms |
101836 KB |
Output is correct |
88 |
Correct |
635 ms |
186860 KB |
Output is correct |
89 |
Correct |
611 ms |
186908 KB |
Output is correct |
90 |
Correct |
613 ms |
187084 KB |
Output is correct |