#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
vector<vector<int>> fen;
void add(bool b, int i, int x){
for(i++; i < sz(fen[0]); i+=i&-i) fen[b][i] += x;
}
int qry(bool b, int i){
int ans = 0;
for(i++; i > 0; i-=i&-i) ans += fen[b][i];
return ans;
}
int qry(bool b, int i, int j){
if(i > 0) return qry(b, j)-qry(b, i-1);
else return qry(b, j);
}
long long count_rectangles(vector<vector<int>> a) {
int n = sz(a), m = sz(a[0]);
vector<vector<short>> r1(n, vector<short>(m, -1)), r2(n, vector<short>(m, -1));
for(int i = 1; i < n-1; i++){
stack<pair<int, int>> st({{a[i][0], 0}});
for(int j = 1; j < m; j++){
while(!st.empty() && a[i][j] > st.top().first){
auto [h, k] = st.top();
st.pop();
r2[i][k] = j-1;
}
if(!st.empty()) {
if(st.top().first > a[i][j]) r1[i][j] = st.top().second+1;
else r1[i][j] = r1[i][st.top().second];
}
st.emplace(a[i][j], j);
}
}
vector<vector<short>> c1(n, vector<short>(m, -1)), c2(n, vector<short>(m, -1));
for(int j = 1; j < m-1; j++){
stack<pair<int, int>> st({{a[0][j], 0}});
for(int i = 1; i < n; i++){
while(!st.empty() && a[i][j] > st.top().first){
auto [h, k] = st.top(); st.pop();
c2[k][j] = i-1;
}
if(!st.empty()){
if(st.top().first > a[i][j]) c1[i][j] = st.top().second+1;
else c1[i][j] = c1[st.top().second][j];
}
st.emplace(a[i][j], i);
}
}
a.clear();
a.shrink_to_fit();
int mx = max(n, m);
fen.resize(2, vector<int>(mx+1));
vector<bool> valid;
vector<vector<tuple<bool, short, short, int>>> queries(mx*mx);
int q = 0, ans = 0;
for(int i = 1; i < n-1; i++){
for(int j = 1; j < m-1; j++){
// cerr << "\n" << i << " " << j << " " << r1[i][j] << " " << r2[i][j] << " " << c1[i][j] << " " << c2[i][j] << "\n";
if(r1[i][j] != -1 && r2[i][j] != -1 && c1[i][j] != -1 && c2[i][j] != -1){
int x = c1[i][j]*mx + c2[i][j], y = r1[i][j]*mx + r2[i][j];
queries[x].emplace_back(0, j, 0, -1);
queries[y].emplace_back(1, i, 0, -1);
valid.push_back(true);
queries[x].emplace_back(0, r1[i][j], r2[i][j], q);
queries[y].emplace_back(1, c1[i][j], c2[i][j], q);
q++;
}
}
}
vector<vector<bool>> used(2, vector<bool>(mx));
vector<vector<bool>> usedQ(2, vector<bool>(mx*mx));
vector<pair<bool, short>> undo;
vector<tuple<bool, short, short, int>> qries;
for(int id = 1; id < mx*mx; id++){
for(auto [b, i, j, ind] : queries[id]){
if(ind == -1){
if(!used[b][i]) add(b, i, 1), undo.emplace_back(b, i);
used[b][i] = true;
}
else qries.emplace_back(b, i, j, ind);
}
for(auto [b, i, j, ind] : qries){
if(usedQ[b][i*mx+j] || qry(b, i, j) != j-i+1) valid[ind] = false;
usedQ[b][i*mx+j] = true;
}
for(auto [b, i, j, ind] : qries) usedQ[b][i*mx+j] = false;
for(auto [b, i] : undo){
add(b, i, -1);
used[b][i] = false;
}
qries.clear();
undo.clear();
}
for(bool b : valid) ans += b;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
2 ms |
980 KB |
Output is correct |
23 |
Correct |
3 ms |
1108 KB |
Output is correct |
24 |
Correct |
3 ms |
980 KB |
Output is correct |
25 |
Correct |
2 ms |
724 KB |
Output is correct |
26 |
Correct |
3 ms |
852 KB |
Output is correct |
27 |
Correct |
3 ms |
868 KB |
Output is correct |
28 |
Correct |
3 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
980 KB |
Output is correct |
18 |
Correct |
3 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
2 ms |
724 KB |
Output is correct |
21 |
Correct |
3 ms |
852 KB |
Output is correct |
22 |
Correct |
3 ms |
868 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
11 ms |
4436 KB |
Output is correct |
31 |
Correct |
13 ms |
4464 KB |
Output is correct |
32 |
Correct |
11 ms |
4604 KB |
Output is correct |
33 |
Correct |
9 ms |
3632 KB |
Output is correct |
34 |
Correct |
15 ms |
4436 KB |
Output is correct |
35 |
Correct |
18 ms |
4592 KB |
Output is correct |
36 |
Correct |
16 ms |
4564 KB |
Output is correct |
37 |
Correct |
14 ms |
4308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
980 KB |
Output is correct |
18 |
Correct |
3 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
2 ms |
724 KB |
Output is correct |
21 |
Correct |
3 ms |
852 KB |
Output is correct |
22 |
Correct |
3 ms |
868 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
11 ms |
4436 KB |
Output is correct |
26 |
Correct |
13 ms |
4464 KB |
Output is correct |
27 |
Correct |
11 ms |
4604 KB |
Output is correct |
28 |
Correct |
9 ms |
3632 KB |
Output is correct |
29 |
Correct |
15 ms |
4436 KB |
Output is correct |
30 |
Correct |
18 ms |
4592 KB |
Output is correct |
31 |
Correct |
16 ms |
4564 KB |
Output is correct |
32 |
Correct |
14 ms |
4308 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
36 ms |
20000 KB |
Output is correct |
39 |
Correct |
37 ms |
20124 KB |
Output is correct |
40 |
Correct |
42 ms |
20048 KB |
Output is correct |
41 |
Correct |
41 ms |
20016 KB |
Output is correct |
42 |
Correct |
138 ms |
48076 KB |
Output is correct |
43 |
Correct |
137 ms |
48588 KB |
Output is correct |
44 |
Correct |
175 ms |
47944 KB |
Output is correct |
45 |
Correct |
131 ms |
46816 KB |
Output is correct |
46 |
Correct |
91 ms |
36436 KB |
Output is correct |
47 |
Correct |
113 ms |
40120 KB |
Output is correct |
48 |
Correct |
229 ms |
47344 KB |
Output is correct |
49 |
Correct |
198 ms |
47292 KB |
Output is correct |
50 |
Correct |
104 ms |
31132 KB |
Output is correct |
51 |
Correct |
122 ms |
30936 KB |
Output is correct |
52 |
Correct |
183 ms |
47948 KB |
Output is correct |
53 |
Correct |
179 ms |
47768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
149584 KB |
Output is correct |
2 |
Correct |
75 ms |
108064 KB |
Output is correct |
3 |
Correct |
100 ms |
149452 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
102 ms |
149472 KB |
Output is correct |
6 |
Correct |
104 ms |
149528 KB |
Output is correct |
7 |
Correct |
101 ms |
149496 KB |
Output is correct |
8 |
Correct |
100 ms |
149452 KB |
Output is correct |
9 |
Correct |
101 ms |
149452 KB |
Output is correct |
10 |
Correct |
95 ms |
149372 KB |
Output is correct |
11 |
Correct |
107 ms |
149600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
702 ms |
259980 KB |
Output is correct |
8 |
Correct |
1581 ms |
427384 KB |
Output is correct |
9 |
Correct |
1609 ms |
430040 KB |
Output is correct |
10 |
Correct |
1448 ms |
428468 KB |
Output is correct |
11 |
Correct |
238 ms |
196164 KB |
Output is correct |
12 |
Correct |
343 ms |
240216 KB |
Output is correct |
13 |
Correct |
375 ms |
246304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
2 ms |
980 KB |
Output is correct |
18 |
Correct |
3 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
980 KB |
Output is correct |
20 |
Correct |
2 ms |
724 KB |
Output is correct |
21 |
Correct |
3 ms |
852 KB |
Output is correct |
22 |
Correct |
3 ms |
868 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
11 ms |
4436 KB |
Output is correct |
26 |
Correct |
13 ms |
4464 KB |
Output is correct |
27 |
Correct |
11 ms |
4604 KB |
Output is correct |
28 |
Correct |
9 ms |
3632 KB |
Output is correct |
29 |
Correct |
15 ms |
4436 KB |
Output is correct |
30 |
Correct |
18 ms |
4592 KB |
Output is correct |
31 |
Correct |
16 ms |
4564 KB |
Output is correct |
32 |
Correct |
14 ms |
4308 KB |
Output is correct |
33 |
Correct |
36 ms |
20000 KB |
Output is correct |
34 |
Correct |
37 ms |
20124 KB |
Output is correct |
35 |
Correct |
42 ms |
20048 KB |
Output is correct |
36 |
Correct |
41 ms |
20016 KB |
Output is correct |
37 |
Correct |
138 ms |
48076 KB |
Output is correct |
38 |
Correct |
137 ms |
48588 KB |
Output is correct |
39 |
Correct |
175 ms |
47944 KB |
Output is correct |
40 |
Correct |
131 ms |
46816 KB |
Output is correct |
41 |
Correct |
91 ms |
36436 KB |
Output is correct |
42 |
Correct |
113 ms |
40120 KB |
Output is correct |
43 |
Correct |
229 ms |
47344 KB |
Output is correct |
44 |
Correct |
198 ms |
47292 KB |
Output is correct |
45 |
Correct |
104 ms |
31132 KB |
Output is correct |
46 |
Correct |
122 ms |
30936 KB |
Output is correct |
47 |
Correct |
183 ms |
47948 KB |
Output is correct |
48 |
Correct |
179 ms |
47768 KB |
Output is correct |
49 |
Correct |
112 ms |
149584 KB |
Output is correct |
50 |
Correct |
75 ms |
108064 KB |
Output is correct |
51 |
Correct |
100 ms |
149452 KB |
Output is correct |
52 |
Correct |
1 ms |
212 KB |
Output is correct |
53 |
Correct |
102 ms |
149472 KB |
Output is correct |
54 |
Correct |
104 ms |
149528 KB |
Output is correct |
55 |
Correct |
101 ms |
149496 KB |
Output is correct |
56 |
Correct |
100 ms |
149452 KB |
Output is correct |
57 |
Correct |
101 ms |
149452 KB |
Output is correct |
58 |
Correct |
95 ms |
149372 KB |
Output is correct |
59 |
Correct |
107 ms |
149600 KB |
Output is correct |
60 |
Correct |
1 ms |
212 KB |
Output is correct |
61 |
Correct |
702 ms |
259980 KB |
Output is correct |
62 |
Correct |
1581 ms |
427384 KB |
Output is correct |
63 |
Correct |
1609 ms |
430040 KB |
Output is correct |
64 |
Correct |
1448 ms |
428468 KB |
Output is correct |
65 |
Correct |
238 ms |
196164 KB |
Output is correct |
66 |
Correct |
343 ms |
240216 KB |
Output is correct |
67 |
Correct |
375 ms |
246304 KB |
Output is correct |
68 |
Correct |
0 ms |
212 KB |
Output is correct |
69 |
Correct |
1 ms |
212 KB |
Output is correct |
70 |
Correct |
1 ms |
340 KB |
Output is correct |
71 |
Correct |
1 ms |
212 KB |
Output is correct |
72 |
Correct |
1 ms |
212 KB |
Output is correct |
73 |
Correct |
541 ms |
245856 KB |
Output is correct |
74 |
Correct |
531 ms |
245948 KB |
Output is correct |
75 |
Correct |
572 ms |
245944 KB |
Output is correct |
76 |
Correct |
515 ms |
245900 KB |
Output is correct |
77 |
Correct |
2209 ms |
609392 KB |
Output is correct |
78 |
Correct |
2027 ms |
421212 KB |
Output is correct |
79 |
Correct |
2057 ms |
441592 KB |
Output is correct |
80 |
Correct |
2955 ms |
587832 KB |
Output is correct |
81 |
Correct |
2049 ms |
450684 KB |
Output is correct |
82 |
Correct |
2712 ms |
546208 KB |
Output is correct |
83 |
Correct |
3262 ms |
635600 KB |
Output is correct |
84 |
Correct |
1690 ms |
443508 KB |
Output is correct |
85 |
Correct |
2907 ms |
640616 KB |
Output is correct |
86 |
Correct |
2918 ms |
628832 KB |
Output is correct |
87 |
Correct |
1414 ms |
441636 KB |
Output is correct |
88 |
Correct |
2289 ms |
651836 KB |
Output is correct |
89 |
Correct |
2315 ms |
654164 KB |
Output is correct |
90 |
Correct |
2321 ms |
654716 KB |
Output is correct |