#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef int64_t lld;
typedef pair<int, int> pii;
/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T, typename comp = greater<T>>
using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
*/
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << "(" << p.ff << ", " << p.ss << ")";
}
vector<pii> tmp;
vector<vector<int>> U, D, L, R;
template<typename Cmp>
struct node{
node *L, *R;
int l, r, mid, s;
int cmp(int a, int b){ return Cmp()(a, b)?a:b; }
vector<int> data;
node(int ll, int rr, int st, const vector<vector<int>>& v) : l(ll), r(rr), mid((l+r)/2), s(st) {
data.resize(s*4);
if(l != r){
L = new node(l, mid, s, v), R = new node(mid+1, r, s, v);
for(int i = 0; i < data.size(); i++)data.at(i) = cmp(L->data.at(i), R->data.at(i));
}
else build_data(1, 0, s, v.at(l));
}
void build_data(int i, int ll, int rr, const vector<int>& v){
if(data.size() <= i)data.resize(i+1);
if(ll == rr)data[i] = v[ll];
else build_data(i<<1, ll, (ll+rr)>>1, v), build_data((i<<1)+1, ((ll+rr)>>1)+1, rr, v), data[i] = cmp(data[i<<1], data[(i<<1)+1]);
}
int query_data(int i, int ll, int rr, int ql, int qr){
//cout << ll << " " << rr << " " << ql << " " << qr << endl;
assert(ql <= rr && qr >= ll);
if(ql <= ll && qr >= rr)return data[i];
if(qr <= ((ll+rr)>>1))return query_data(i<<1, ll, (ll+rr)>>1, ql, qr);
if(ql > ((ll+rr)>>1))return query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr);
return cmp(query_data(i<<1, ll, (ll+rr)>>1, ql, qr), query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr));
}
int query(int l1, int r1, int l2, int r2){
assert(l1 <= r && r1 >= l);
if(l1 <= l && r1 >= r)return query_data(1, 0, s, l2, r2);
if(l1 > mid)return R->query(l1, r1, l2, r2);
if(r1 <= mid)return L->query(l1, r1, l2, r2);
return cmp(L->query(l1, r1, l2, r2), R->query(l1, r1, l2, r2));
}
};
node<greater<int>> *d, *r;
node<less<int>> *u, *l;
set<tuple<int, int, int, int>> st;
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
U = D = L = R = a;
for(int i = 1; i < n; i++){
tmp.resize(0); tmp.pb({INT_MAX, -1});
for(int j = 0; j < m; j++){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
L[i][j] = tmp.back().ss;
tmp.pb({a[i][j], j});
}
tmp.resize(0); tmp.pb({INT_MAX, m});
for(int j = m-1; j > 0; j--){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
R[i][j] = tmp.back().ss;
tmp.pb({a[i][j], j});
}
}
for(int j = 1; j < m; j++){
tmp.resize(0); tmp.pb({INT_MAX, -1});
for(int i = 0; i < n; i++){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
U[i][j] = tmp.back().ss;
tmp.pb({a[i][j], i});
}
tmp.resize(0); tmp.pb({INT_MAX, n});
for(int i = n-1; i > 0; i--){
while(tmp.back().ff <= a[i][j])tmp.pop_back();
D[i][j] = tmp.back().ss;
tmp.pb({a[i][j], i});
}
}
u = new node<less<int>>(0, n-1, m-1, U), l = new node<less<int>>(0, n-1, m-1, L);
d = new node<greater<int>>(0, n-1, m-1, D), r = new node<greater<int>>(0, n-1, m-1, R);
for(int i = 1; i <= n-2; i++)
for(int j = 1; j <= m-2; j++){
if(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m)goto next;
//cout << i << " " << j << " " << U[i][j] << D[i][j] << L[i][j] << R[i][j] << " " << u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) << endl;
if(u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != U[i][j])goto next;
if(l->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != L[i][j])goto next;
if(d->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != D[i][j])goto next;
if(r->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != R[i][j])goto next;
st.insert({U[i][j], L[i][j], D[i][j], R[i][j]});
next:;
}
return st.size();
}
Compilation message
rect.cpp: In instantiation of 'node<Cmp>::node(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]':
rect.cpp:98:40: required from here
rect.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0; i < data.size(); i++)data.at(i) = cmp(L->data.at(i), R->data.at(i));
| ~~^~~~~~~~~~~~~
rect.cpp: In instantiation of 'node<Cmp>::node(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]':
rect.cpp:99:43: required from here
rect.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
rect.cpp: In instantiation of 'void node<Cmp>::build_data(int, int, int, const std::vector<int>&) [with Cmp = std::less<int>]':
rect.cpp:38:8: required from 'node<Cmp>::node(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]'
rect.cpp:98:40: required from here
rect.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | if(data.size() <= i)data.resize(i+1);
| ~~~~~~~~~~~~^~~~
rect.cpp: In instantiation of 'void node<Cmp>::build_data(int, int, int, const std::vector<int>&) [with Cmp = std::greater<int>]':
rect.cpp:38:8: required from 'node<Cmp>::node(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]'
rect.cpp:99:43: required from here
rect.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
13 ms |
1664 KB |
Output is correct |
18 |
Correct |
14 ms |
1664 KB |
Output is correct |
19 |
Correct |
18 ms |
1792 KB |
Output is correct |
20 |
Correct |
3 ms |
1408 KB |
Output is correct |
21 |
Correct |
5 ms |
1496 KB |
Output is correct |
22 |
Correct |
5 ms |
1408 KB |
Output is correct |
23 |
Correct |
5 ms |
1408 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
512 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
13 ms |
1664 KB |
Output is correct |
18 |
Correct |
14 ms |
1664 KB |
Output is correct |
19 |
Correct |
18 ms |
1792 KB |
Output is correct |
20 |
Correct |
3 ms |
1408 KB |
Output is correct |
21 |
Correct |
5 ms |
1496 KB |
Output is correct |
22 |
Correct |
5 ms |
1408 KB |
Output is correct |
23 |
Correct |
5 ms |
1408 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
122 ms |
8988 KB |
Output is correct |
26 |
Correct |
122 ms |
8824 KB |
Output is correct |
27 |
Correct |
129 ms |
8824 KB |
Output is correct |
28 |
Correct |
21 ms |
6656 KB |
Output is correct |
29 |
Correct |
29 ms |
7160 KB |
Output is correct |
30 |
Correct |
32 ms |
7160 KB |
Output is correct |
31 |
Correct |
37 ms |
7160 KB |
Output is correct |
32 |
Correct |
34 ms |
7160 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
1 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
512 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
13 ms |
1664 KB |
Output is correct |
18 |
Correct |
14 ms |
1664 KB |
Output is correct |
19 |
Correct |
18 ms |
1792 KB |
Output is correct |
20 |
Correct |
3 ms |
1408 KB |
Output is correct |
21 |
Correct |
5 ms |
1496 KB |
Output is correct |
22 |
Correct |
5 ms |
1408 KB |
Output is correct |
23 |
Correct |
5 ms |
1408 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
122 ms |
8988 KB |
Output is correct |
26 |
Correct |
122 ms |
8824 KB |
Output is correct |
27 |
Correct |
129 ms |
8824 KB |
Output is correct |
28 |
Correct |
21 ms |
6656 KB |
Output is correct |
29 |
Correct |
29 ms |
7160 KB |
Output is correct |
30 |
Correct |
32 ms |
7160 KB |
Output is correct |
31 |
Correct |
37 ms |
7160 KB |
Output is correct |
32 |
Correct |
34 ms |
7160 KB |
Output is correct |
33 |
Correct |
135 ms |
73720 KB |
Output is correct |
34 |
Correct |
134 ms |
73720 KB |
Output is correct |
35 |
Correct |
134 ms |
73784 KB |
Output is correct |
36 |
Correct |
131 ms |
73832 KB |
Output is correct |
37 |
Correct |
2643 ms |
104312 KB |
Output is correct |
38 |
Correct |
2655 ms |
104164 KB |
Output is correct |
39 |
Correct |
2652 ms |
104296 KB |
Output is correct |
40 |
Correct |
2521 ms |
97412 KB |
Output is correct |
41 |
Correct |
236 ms |
74872 KB |
Output is correct |
42 |
Correct |
291 ms |
76668 KB |
Output is correct |
43 |
Correct |
469 ms |
84088 KB |
Output is correct |
44 |
Correct |
469 ms |
84064 KB |
Output is correct |
45 |
Correct |
204 ms |
42360 KB |
Output is correct |
46 |
Correct |
223 ms |
42196 KB |
Output is correct |
47 |
Correct |
623 ms |
84088 KB |
Output is correct |
48 |
Correct |
611 ms |
84088 KB |
Output is correct |
49 |
Correct |
0 ms |
256 KB |
Output is correct |
50 |
Correct |
1 ms |
256 KB |
Output is correct |
51 |
Correct |
1 ms |
512 KB |
Output is correct |
52 |
Correct |
1 ms |
384 KB |
Output is correct |
53 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1440 KB |
Output is correct |
2 |
Correct |
4 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
1280 KB |
Output is correct |
6 |
Correct |
3 ms |
1280 KB |
Output is correct |
7 |
Correct |
3 ms |
1280 KB |
Output is correct |
8 |
Correct |
2 ms |
1280 KB |
Output is correct |
9 |
Correct |
3 ms |
1280 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1380 ms |
434296 KB |
Output is correct |
3 |
Correct |
3024 ms |
942516 KB |
Output is correct |
4 |
Correct |
3028 ms |
950972 KB |
Output is correct |
5 |
Correct |
3063 ms |
951428 KB |
Output is correct |
6 |
Correct |
836 ms |
464072 KB |
Output is correct |
7 |
Correct |
1533 ms |
878328 KB |
Output is correct |
8 |
Correct |
1627 ms |
935804 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1 ms |
512 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
13 ms |
1664 KB |
Output is correct |
18 |
Correct |
14 ms |
1664 KB |
Output is correct |
19 |
Correct |
18 ms |
1792 KB |
Output is correct |
20 |
Correct |
3 ms |
1408 KB |
Output is correct |
21 |
Correct |
5 ms |
1496 KB |
Output is correct |
22 |
Correct |
5 ms |
1408 KB |
Output is correct |
23 |
Correct |
5 ms |
1408 KB |
Output is correct |
24 |
Correct |
3 ms |
896 KB |
Output is correct |
25 |
Correct |
122 ms |
8988 KB |
Output is correct |
26 |
Correct |
122 ms |
8824 KB |
Output is correct |
27 |
Correct |
129 ms |
8824 KB |
Output is correct |
28 |
Correct |
21 ms |
6656 KB |
Output is correct |
29 |
Correct |
29 ms |
7160 KB |
Output is correct |
30 |
Correct |
32 ms |
7160 KB |
Output is correct |
31 |
Correct |
37 ms |
7160 KB |
Output is correct |
32 |
Correct |
34 ms |
7160 KB |
Output is correct |
33 |
Correct |
135 ms |
73720 KB |
Output is correct |
34 |
Correct |
134 ms |
73720 KB |
Output is correct |
35 |
Correct |
134 ms |
73784 KB |
Output is correct |
36 |
Correct |
131 ms |
73832 KB |
Output is correct |
37 |
Correct |
2643 ms |
104312 KB |
Output is correct |
38 |
Correct |
2655 ms |
104164 KB |
Output is correct |
39 |
Correct |
2652 ms |
104296 KB |
Output is correct |
40 |
Correct |
2521 ms |
97412 KB |
Output is correct |
41 |
Correct |
236 ms |
74872 KB |
Output is correct |
42 |
Correct |
291 ms |
76668 KB |
Output is correct |
43 |
Correct |
469 ms |
84088 KB |
Output is correct |
44 |
Correct |
469 ms |
84064 KB |
Output is correct |
45 |
Correct |
204 ms |
42360 KB |
Output is correct |
46 |
Correct |
223 ms |
42196 KB |
Output is correct |
47 |
Correct |
623 ms |
84088 KB |
Output is correct |
48 |
Correct |
611 ms |
84088 KB |
Output is correct |
49 |
Correct |
4 ms |
1440 KB |
Output is correct |
50 |
Correct |
4 ms |
1280 KB |
Output is correct |
51 |
Correct |
2 ms |
1280 KB |
Output is correct |
52 |
Correct |
0 ms |
256 KB |
Output is correct |
53 |
Correct |
3 ms |
1280 KB |
Output is correct |
54 |
Correct |
3 ms |
1280 KB |
Output is correct |
55 |
Correct |
3 ms |
1280 KB |
Output is correct |
56 |
Correct |
2 ms |
1280 KB |
Output is correct |
57 |
Correct |
3 ms |
1280 KB |
Output is correct |
58 |
Correct |
1 ms |
512 KB |
Output is correct |
59 |
Correct |
2 ms |
896 KB |
Output is correct |
60 |
Correct |
0 ms |
384 KB |
Output is correct |
61 |
Correct |
1380 ms |
434296 KB |
Output is correct |
62 |
Correct |
3024 ms |
942516 KB |
Output is correct |
63 |
Correct |
3028 ms |
950972 KB |
Output is correct |
64 |
Correct |
3063 ms |
951428 KB |
Output is correct |
65 |
Correct |
836 ms |
464072 KB |
Output is correct |
66 |
Correct |
1533 ms |
878328 KB |
Output is correct |
67 |
Correct |
1627 ms |
935804 KB |
Output is correct |
68 |
Correct |
1762 ms |
931724 KB |
Output is correct |
69 |
Correct |
1782 ms |
931800 KB |
Output is correct |
70 |
Correct |
1762 ms |
931856 KB |
Output is correct |
71 |
Correct |
1787 ms |
931960 KB |
Output is correct |
72 |
Execution timed out |
5146 ms |
952936 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |