#include "rect.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 2510;
int n, m;
vector< vector<int> > a;
vector<pii> segC[N];
vector<int> segR[N][N];
vector<int> eqr[N];
void PrepCol(int j){
vector<int> A(n);
for(int i = 0; i < n; i++) A[i] = a[i][j];
stack<int> st;
for(int i = 0; i < n; i++){
while(!st.empty() && A[st.top()] < A[i]) st.pop();
if(!st.empty() && i - st.top() > 1)
segC[j].pb({st.top(), i});
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && A[st.top()] < A[i]) st.pop();
if(!st.empty() && st.top() - i > 1)
segC[j].pb({i, st.top()});
st.push(i);
}
sort(all(segC[j]));
segC[j].resize(unique(all(segC[j])) - segC[j].begin());
for(int i = 0; i + 1 < (int) segC[j].size(); i++){
if(segC[j][i].F < segC[j][i + 1].F && segC[j][i + 1].F < segC[j][i].S && segC[j][i].S < segC[j][i + 1].S)
assert(0);
}
// assert((segC[j][i].S <= segC[j][i + 1].S) || );
/*
cerr << "col : " << j << '\n';
for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
cerr << '\n';
*/
}
void PrepRow(int i){
vector<int> A(m);
for(int j = 0; j < m; j++) A[j] = a[i][j];
stack<int> st;
vector<pii> seg;
for(int j = 0; j < m; j++){
while(!st.empty() && A[st.top()] < A[j]) st.pop();
if(!st.empty() && j - st.top() > 1)
seg.pb({st.top(), j});
st.push(j);
}
while(!st.empty()) st.pop();
for(int j = m - 1; j >= 0; j--){
while(!st.empty() && A[st.top()] < A[j]) st.pop();
if(!st.empty() && st.top() - j > 1)
seg.pb({j, st.top()});
st.push(j);
}
sort(all(seg));
seg.resize(unique(all(seg)) - seg.begin());
/*
for(int i = 0; i + 1 < (int) seg.size(); i++)
assert(seg[i].S <= seg[i + 1].S);
*/
for(auto X : seg) segR[X.F][X.S].pb(i);
/*
cerr << "col : " << j << '\n';
for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
cerr << '\n';
*/
}
vector<int> ev[N];
vector<pii> Fen;
int fen[N][N];
void Add(int fn, int idx, int d){
idx ++;
for(; idx < N - 1; idx += idx & (-idx))
fen[fn][idx] += d;
fen[fn][N - 1] += d;
}
int Get(int fn, int idx){
int res = fen[fn][N - 1];
for(; idx; idx -= idx & (-idx))
res -= fen[fn][idx];
return res;
}
void Add(pii x){
Add(x.S, x.F, +1);
//Fen.pb(x);
}
void Rem(pii x){
Add(x.S, x.F, -1);
/*
for(int i = 0; i + 1 < (int) Fen.size(); i++){
if(Fen[i] == x) swap(Fen[i], Fen[i + 1]);
}
if(Fen.back() == x)
Fen.pop_back();
*/
}
int Get(pii x){
return Get(x.S, x.F);
int res = 0;
for(auto &y : Fen){
if(x.F <= y.F && y.S == x.S)
res ++;
}
return res;
}
ll count_rectangles(vector<vector<int> > _a){
a = _a;
n = a.size();
m = a[0].size();
cerr << "! " << n << ' ' << m << '\n';
for(int i = 1; i < m - 1; i++) PrepCol(i);
for(int i = 1; i < n - 1; i++) PrepRow(i);
//
int cnt, idx;
for(int j = m - 1; j >= 1; j--){
cnt = segC[j].size();
eqr[j].resize(cnt);
for(int i = 0; i < cnt; i++){
idx = lower_bound(all(segC[j + 1]), segC[j][i]) - segC[j + 1].begin();
eqr[j][i] = (idx == (int)segC[j + 1].size() || segC[j + 1][idx] != segC[j][i] ? 1 : eqr[j + 1][idx] + 1);
//cerr << segC[j][i].F << ", " << segC[j][i].S << " -> " << eqr[j][i] << '\n';
}
}
ll ans = 0;
for(int j1 = 1; j1 < m - 1; j1 ++){
for(int j2 = j1; j2 < m - 1; j2 ++)
ev[j2].clear();
Fen.clear();
cnt = segC[j1].size();
for(int i = 0; i < cnt; i++){
Add(segC[j1][i]);
ev[j1 + eqr[j1][i] - 1].pb(i);
}
for(int j2 = j1; j2 < m - 1; j2 ++){
vector<int> &R = segR[j1 - 1][j2 + 1];
//R.pb(-1);
int con = 1;
for(int i = 0; i < (int) R.size(); i++){
if(i == 0) con = 1;
else if(R[i] == R[i - 1] + 1) con ++;
else {
//ans += Get({R[i - 1] - con, R[i - 1] + 1});
con = 1;
}
ans += Get({R[i] - con, R[i] + 1});
}
for(auto id : ev[j2])
Rem(segC[j1][id]);
}
assert(Fen.empty());
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
148472 KB |
Output is correct |
2 |
Correct |
93 ms |
148472 KB |
Output is correct |
3 |
Correct |
96 ms |
148472 KB |
Output is correct |
4 |
Correct |
94 ms |
148472 KB |
Output is correct |
5 |
Correct |
92 ms |
148472 KB |
Output is correct |
6 |
Correct |
95 ms |
148756 KB |
Output is correct |
7 |
Correct |
96 ms |
148700 KB |
Output is correct |
8 |
Correct |
93 ms |
148600 KB |
Output is correct |
9 |
Correct |
100 ms |
148728 KB |
Output is correct |
10 |
Correct |
95 ms |
148728 KB |
Output is correct |
11 |
Correct |
93 ms |
148860 KB |
Output is correct |
12 |
Correct |
95 ms |
148728 KB |
Output is correct |
13 |
Correct |
96 ms |
148472 KB |
Output is correct |
14 |
Correct |
95 ms |
148472 KB |
Output is correct |
15 |
Correct |
92 ms |
148472 KB |
Output is correct |
16 |
Correct |
92 ms |
148472 KB |
Output is correct |
17 |
Correct |
92 ms |
148504 KB |
Output is correct |
18 |
Correct |
96 ms |
148600 KB |
Output is correct |
19 |
Correct |
93 ms |
148728 KB |
Output is correct |
20 |
Correct |
98 ms |
148508 KB |
Output is correct |
21 |
Correct |
95 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
148472 KB |
Output is correct |
2 |
Correct |
93 ms |
148472 KB |
Output is correct |
3 |
Correct |
96 ms |
148472 KB |
Output is correct |
4 |
Correct |
94 ms |
148472 KB |
Output is correct |
5 |
Correct |
92 ms |
148472 KB |
Output is correct |
6 |
Correct |
95 ms |
148756 KB |
Output is correct |
7 |
Correct |
96 ms |
148700 KB |
Output is correct |
8 |
Correct |
93 ms |
148600 KB |
Output is correct |
9 |
Correct |
100 ms |
148728 KB |
Output is correct |
10 |
Correct |
95 ms |
148728 KB |
Output is correct |
11 |
Correct |
93 ms |
148860 KB |
Output is correct |
12 |
Correct |
95 ms |
148728 KB |
Output is correct |
13 |
Correct |
96 ms |
148472 KB |
Output is correct |
14 |
Correct |
95 ms |
148472 KB |
Output is correct |
15 |
Correct |
92 ms |
148472 KB |
Output is correct |
16 |
Correct |
92 ms |
148472 KB |
Output is correct |
17 |
Correct |
94 ms |
148728 KB |
Output is correct |
18 |
Correct |
96 ms |
148876 KB |
Output is correct |
19 |
Correct |
93 ms |
148728 KB |
Output is correct |
20 |
Correct |
96 ms |
149320 KB |
Output is correct |
21 |
Correct |
94 ms |
149496 KB |
Output is correct |
22 |
Correct |
94 ms |
149496 KB |
Output is correct |
23 |
Correct |
98 ms |
149496 KB |
Output is correct |
24 |
Correct |
93 ms |
149368 KB |
Output is correct |
25 |
Correct |
92 ms |
148504 KB |
Output is correct |
26 |
Correct |
96 ms |
148600 KB |
Output is correct |
27 |
Correct |
93 ms |
148728 KB |
Output is correct |
28 |
Correct |
98 ms |
148508 KB |
Output is correct |
29 |
Correct |
95 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
148472 KB |
Output is correct |
2 |
Correct |
93 ms |
148472 KB |
Output is correct |
3 |
Correct |
96 ms |
148472 KB |
Output is correct |
4 |
Correct |
94 ms |
148472 KB |
Output is correct |
5 |
Correct |
92 ms |
148472 KB |
Output is correct |
6 |
Correct |
95 ms |
148756 KB |
Output is correct |
7 |
Correct |
96 ms |
148700 KB |
Output is correct |
8 |
Correct |
93 ms |
148600 KB |
Output is correct |
9 |
Correct |
100 ms |
148728 KB |
Output is correct |
10 |
Correct |
95 ms |
148728 KB |
Output is correct |
11 |
Correct |
93 ms |
148860 KB |
Output is correct |
12 |
Correct |
95 ms |
148728 KB |
Output is correct |
13 |
Correct |
96 ms |
148472 KB |
Output is correct |
14 |
Correct |
95 ms |
148472 KB |
Output is correct |
15 |
Correct |
92 ms |
148472 KB |
Output is correct |
16 |
Correct |
92 ms |
148472 KB |
Output is correct |
17 |
Correct |
94 ms |
148728 KB |
Output is correct |
18 |
Correct |
96 ms |
148876 KB |
Output is correct |
19 |
Correct |
93 ms |
148728 KB |
Output is correct |
20 |
Correct |
96 ms |
149320 KB |
Output is correct |
21 |
Correct |
94 ms |
149496 KB |
Output is correct |
22 |
Correct |
94 ms |
149496 KB |
Output is correct |
23 |
Correct |
98 ms |
149496 KB |
Output is correct |
24 |
Correct |
93 ms |
149368 KB |
Output is correct |
25 |
Correct |
102 ms |
149752 KB |
Output is correct |
26 |
Correct |
103 ms |
149752 KB |
Output is correct |
27 |
Correct |
101 ms |
149752 KB |
Output is correct |
28 |
Correct |
104 ms |
151544 KB |
Output is correct |
29 |
Correct |
111 ms |
151928 KB |
Output is correct |
30 |
Correct |
111 ms |
152060 KB |
Output is correct |
31 |
Correct |
112 ms |
151804 KB |
Output is correct |
32 |
Correct |
109 ms |
151804 KB |
Output is correct |
33 |
Correct |
92 ms |
148504 KB |
Output is correct |
34 |
Correct |
96 ms |
148600 KB |
Output is correct |
35 |
Correct |
93 ms |
148728 KB |
Output is correct |
36 |
Correct |
98 ms |
148508 KB |
Output is correct |
37 |
Correct |
95 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
148472 KB |
Output is correct |
2 |
Correct |
93 ms |
148472 KB |
Output is correct |
3 |
Correct |
96 ms |
148472 KB |
Output is correct |
4 |
Correct |
94 ms |
148472 KB |
Output is correct |
5 |
Correct |
92 ms |
148472 KB |
Output is correct |
6 |
Correct |
95 ms |
148756 KB |
Output is correct |
7 |
Correct |
96 ms |
148700 KB |
Output is correct |
8 |
Correct |
93 ms |
148600 KB |
Output is correct |
9 |
Correct |
100 ms |
148728 KB |
Output is correct |
10 |
Correct |
95 ms |
148728 KB |
Output is correct |
11 |
Correct |
93 ms |
148860 KB |
Output is correct |
12 |
Correct |
95 ms |
148728 KB |
Output is correct |
13 |
Correct |
96 ms |
148472 KB |
Output is correct |
14 |
Correct |
95 ms |
148472 KB |
Output is correct |
15 |
Correct |
92 ms |
148472 KB |
Output is correct |
16 |
Correct |
92 ms |
148472 KB |
Output is correct |
17 |
Correct |
94 ms |
148728 KB |
Output is correct |
18 |
Correct |
96 ms |
148876 KB |
Output is correct |
19 |
Correct |
93 ms |
148728 KB |
Output is correct |
20 |
Correct |
96 ms |
149320 KB |
Output is correct |
21 |
Correct |
94 ms |
149496 KB |
Output is correct |
22 |
Correct |
94 ms |
149496 KB |
Output is correct |
23 |
Correct |
98 ms |
149496 KB |
Output is correct |
24 |
Correct |
93 ms |
149368 KB |
Output is correct |
25 |
Correct |
102 ms |
149752 KB |
Output is correct |
26 |
Correct |
103 ms |
149752 KB |
Output is correct |
27 |
Correct |
101 ms |
149752 KB |
Output is correct |
28 |
Correct |
104 ms |
151544 KB |
Output is correct |
29 |
Correct |
111 ms |
151928 KB |
Output is correct |
30 |
Correct |
111 ms |
152060 KB |
Output is correct |
31 |
Correct |
112 ms |
151804 KB |
Output is correct |
32 |
Correct |
109 ms |
151804 KB |
Output is correct |
33 |
Correct |
194 ms |
174196 KB |
Output is correct |
34 |
Correct |
188 ms |
174072 KB |
Output is correct |
35 |
Correct |
202 ms |
174072 KB |
Output is correct |
36 |
Correct |
182 ms |
174072 KB |
Output is correct |
37 |
Correct |
212 ms |
164672 KB |
Output is correct |
38 |
Correct |
210 ms |
164600 KB |
Output is correct |
39 |
Correct |
210 ms |
164760 KB |
Output is correct |
40 |
Correct |
200 ms |
164216 KB |
Output is correct |
41 |
Correct |
175 ms |
166012 KB |
Output is correct |
42 |
Correct |
219 ms |
166776 KB |
Output is correct |
43 |
Correct |
316 ms |
174584 KB |
Output is correct |
44 |
Correct |
329 ms |
174840 KB |
Output is correct |
45 |
Correct |
205 ms |
164984 KB |
Output is correct |
46 |
Correct |
210 ms |
161760 KB |
Output is correct |
47 |
Correct |
301 ms |
172408 KB |
Output is correct |
48 |
Correct |
309 ms |
172756 KB |
Output is correct |
49 |
Correct |
92 ms |
148504 KB |
Output is correct |
50 |
Correct |
96 ms |
148600 KB |
Output is correct |
51 |
Correct |
93 ms |
148728 KB |
Output is correct |
52 |
Correct |
98 ms |
148508 KB |
Output is correct |
53 |
Correct |
95 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
148728 KB |
Output is correct |
2 |
Correct |
107 ms |
148856 KB |
Output is correct |
3 |
Correct |
110 ms |
148728 KB |
Output is correct |
4 |
Correct |
96 ms |
148472 KB |
Output is correct |
5 |
Correct |
109 ms |
148732 KB |
Output is correct |
6 |
Correct |
111 ms |
148728 KB |
Output is correct |
7 |
Correct |
110 ms |
148728 KB |
Output is correct |
8 |
Correct |
110 ms |
148728 KB |
Output is correct |
9 |
Correct |
110 ms |
148788 KB |
Output is correct |
10 |
Correct |
109 ms |
148472 KB |
Output is correct |
11 |
Correct |
121 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
148472 KB |
Output is correct |
2 |
Correct |
656 ms |
225400 KB |
Output is correct |
3 |
Correct |
1324 ms |
303292 KB |
Output is correct |
4 |
Correct |
1341 ms |
303736 KB |
Output is correct |
5 |
Correct |
1329 ms |
303608 KB |
Output is correct |
6 |
Correct |
240 ms |
184824 KB |
Output is correct |
7 |
Correct |
408 ms |
217592 KB |
Output is correct |
8 |
Correct |
424 ms |
222200 KB |
Output is correct |
9 |
Correct |
92 ms |
148504 KB |
Output is correct |
10 |
Correct |
96 ms |
148600 KB |
Output is correct |
11 |
Correct |
93 ms |
148728 KB |
Output is correct |
12 |
Correct |
98 ms |
148508 KB |
Output is correct |
13 |
Correct |
95 ms |
148472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
148472 KB |
Output is correct |
2 |
Correct |
93 ms |
148472 KB |
Output is correct |
3 |
Correct |
96 ms |
148472 KB |
Output is correct |
4 |
Correct |
94 ms |
148472 KB |
Output is correct |
5 |
Correct |
92 ms |
148472 KB |
Output is correct |
6 |
Correct |
95 ms |
148756 KB |
Output is correct |
7 |
Correct |
96 ms |
148700 KB |
Output is correct |
8 |
Correct |
93 ms |
148600 KB |
Output is correct |
9 |
Correct |
100 ms |
148728 KB |
Output is correct |
10 |
Correct |
95 ms |
148728 KB |
Output is correct |
11 |
Correct |
93 ms |
148860 KB |
Output is correct |
12 |
Correct |
95 ms |
148728 KB |
Output is correct |
13 |
Correct |
96 ms |
148472 KB |
Output is correct |
14 |
Correct |
95 ms |
148472 KB |
Output is correct |
15 |
Correct |
92 ms |
148472 KB |
Output is correct |
16 |
Correct |
92 ms |
148472 KB |
Output is correct |
17 |
Correct |
94 ms |
148728 KB |
Output is correct |
18 |
Correct |
96 ms |
148876 KB |
Output is correct |
19 |
Correct |
93 ms |
148728 KB |
Output is correct |
20 |
Correct |
96 ms |
149320 KB |
Output is correct |
21 |
Correct |
94 ms |
149496 KB |
Output is correct |
22 |
Correct |
94 ms |
149496 KB |
Output is correct |
23 |
Correct |
98 ms |
149496 KB |
Output is correct |
24 |
Correct |
93 ms |
149368 KB |
Output is correct |
25 |
Correct |
102 ms |
149752 KB |
Output is correct |
26 |
Correct |
103 ms |
149752 KB |
Output is correct |
27 |
Correct |
101 ms |
149752 KB |
Output is correct |
28 |
Correct |
104 ms |
151544 KB |
Output is correct |
29 |
Correct |
111 ms |
151928 KB |
Output is correct |
30 |
Correct |
111 ms |
152060 KB |
Output is correct |
31 |
Correct |
112 ms |
151804 KB |
Output is correct |
32 |
Correct |
109 ms |
151804 KB |
Output is correct |
33 |
Correct |
194 ms |
174196 KB |
Output is correct |
34 |
Correct |
188 ms |
174072 KB |
Output is correct |
35 |
Correct |
202 ms |
174072 KB |
Output is correct |
36 |
Correct |
182 ms |
174072 KB |
Output is correct |
37 |
Correct |
212 ms |
164672 KB |
Output is correct |
38 |
Correct |
210 ms |
164600 KB |
Output is correct |
39 |
Correct |
210 ms |
164760 KB |
Output is correct |
40 |
Correct |
200 ms |
164216 KB |
Output is correct |
41 |
Correct |
175 ms |
166012 KB |
Output is correct |
42 |
Correct |
219 ms |
166776 KB |
Output is correct |
43 |
Correct |
316 ms |
174584 KB |
Output is correct |
44 |
Correct |
329 ms |
174840 KB |
Output is correct |
45 |
Correct |
205 ms |
164984 KB |
Output is correct |
46 |
Correct |
210 ms |
161760 KB |
Output is correct |
47 |
Correct |
301 ms |
172408 KB |
Output is correct |
48 |
Correct |
309 ms |
172756 KB |
Output is correct |
49 |
Correct |
113 ms |
148728 KB |
Output is correct |
50 |
Correct |
107 ms |
148856 KB |
Output is correct |
51 |
Correct |
110 ms |
148728 KB |
Output is correct |
52 |
Correct |
96 ms |
148472 KB |
Output is correct |
53 |
Correct |
109 ms |
148732 KB |
Output is correct |
54 |
Correct |
111 ms |
148728 KB |
Output is correct |
55 |
Correct |
110 ms |
148728 KB |
Output is correct |
56 |
Correct |
110 ms |
148728 KB |
Output is correct |
57 |
Correct |
110 ms |
148788 KB |
Output is correct |
58 |
Correct |
109 ms |
148472 KB |
Output is correct |
59 |
Correct |
121 ms |
148472 KB |
Output is correct |
60 |
Correct |
94 ms |
148472 KB |
Output is correct |
61 |
Correct |
656 ms |
225400 KB |
Output is correct |
62 |
Correct |
1324 ms |
303292 KB |
Output is correct |
63 |
Correct |
1341 ms |
303736 KB |
Output is correct |
64 |
Correct |
1329 ms |
303608 KB |
Output is correct |
65 |
Correct |
240 ms |
184824 KB |
Output is correct |
66 |
Correct |
408 ms |
217592 KB |
Output is correct |
67 |
Correct |
424 ms |
222200 KB |
Output is correct |
68 |
Correct |
1830 ms |
407520 KB |
Output is correct |
69 |
Correct |
1260 ms |
407288 KB |
Output is correct |
70 |
Correct |
1868 ms |
407496 KB |
Output is correct |
71 |
Correct |
1324 ms |
407416 KB |
Output is correct |
72 |
Correct |
1886 ms |
345068 KB |
Output is correct |
73 |
Correct |
2031 ms |
307464 KB |
Output is correct |
74 |
Correct |
2159 ms |
318580 KB |
Output is correct |
75 |
Correct |
3328 ms |
394180 KB |
Output is correct |
76 |
Correct |
2091 ms |
308504 KB |
Output is correct |
77 |
Correct |
2820 ms |
354848 KB |
Output is correct |
78 |
Correct |
3479 ms |
400280 KB |
Output is correct |
79 |
Correct |
1895 ms |
290492 KB |
Output is correct |
80 |
Correct |
3228 ms |
377032 KB |
Output is correct |
81 |
Correct |
3138 ms |
371356 KB |
Output is correct |
82 |
Correct |
1139 ms |
267556 KB |
Output is correct |
83 |
Correct |
1898 ms |
345128 KB |
Output is correct |
84 |
Correct |
1886 ms |
344756 KB |
Output is correct |
85 |
Correct |
1869 ms |
343752 KB |
Output is correct |
86 |
Correct |
92 ms |
148504 KB |
Output is correct |
87 |
Correct |
96 ms |
148600 KB |
Output is correct |
88 |
Correct |
93 ms |
148728 KB |
Output is correct |
89 |
Correct |
98 ms |
148508 KB |
Output is correct |
90 |
Correct |
95 ms |
148472 KB |
Output is correct |