#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; // PAMIETAC, ZE TAM MAM CIAG INDEKSOWANY OD 0
struct segminmax{
int base;
struct Node{
int mn, mx;
Node(){ mn = inf, mx = 0; }
};
vv<Node> t;
void init(int n, vv<int> &a, vv<int> &b){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, Node());
for(int i = 1; i <= n; ++i) t[i+base-1].mn = b[i-1], t[i+base-1].mx = a[i-1];
for(int i = base-1; i; --i) t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn), t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
}
int query_interval_min(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i].mn;
int mid = (s+e)>>1, result = inf;
if(x <= mid) result = min(result, query_interval_min(i<<1, s, mid, x, y));
if(mid < y) result = min(result, query_interval_min(i<<1|1, mid+1, e, x, y));
return result;
}
int query_interval_max(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i].mx;
int mid = (s+e)>>1, result = 0;
if(x <= mid) result = max(result, query_interval_max(i<<1, s, mid, x, y));
if(mid < y) result = max(result, query_interval_max(i<<1|1, mid+1, e, x, y));
return result;
}
int query_min(int l, int r){
if(l <= r) return query_interval_min(1, 1, base, max(1, l), min(base, r));
return 0;
}
int query_max(int l, int r){
if(l <= r) return query_interval_max(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
struct seg{
int base;
vv<int> t;
void init(int n){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, 0);
}
void update(int i, int val){
for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
}
int query_interval(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i];
int mid = (s+e)>>1, result = 0;
if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
return result;
}
int query(int l, int r){
if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
ll count_rectangles(vv<vv<int>> t){
int n = ssize(t), m = ssize(t[0]);
vv<vv<int>> u(n, vv<int>(m, 0)), d(n, vv<int>(m, n-1));
vv<map<pii, int>> mp(n);
vv<int> st;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){ // przedzialy gdzie ja to prawy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(st.back(), j)] = 1;
st.emplace_back(j);
} st = vv<int>();
for(int j = m-1; ~j; --j){ // przedzialy gdzie ja to lewy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(j, st.back())] = 1;
st.emplace_back(j);
} st = vv<int>();
}
for(int j = 0; j < m; ++j){
for(int i = 0; i < n; ++i){ // przedzialy gdzie ja to dolny koniec (ustawiamy najblizszego do gory)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) u[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
for(int i = n-1; ~i; --i){ // przedzialy gdzie ja to gorny koniec (ustawiamy najblizszego na dole)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) d[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
}
//~ for(int i = 0; i < n; ++i){
//~ for(int j = 0; j < m; ++j) printf("%d ", d[i][j]);
//~ pn;
//~ }
ll result = 0;
vv<segminmax> segm(n);
vv<vv<int>> rem(n+1);
seg seg; seg.init(n);
for(int i = 0; i < n; ++i) segm[i].init(m, u[i], d[i]);
for(int i = 1; i < n-1; ++i){
for(pair<pii, int> pd : mp[i]) if(pd.se){
int l = pd.fi.fi+1, r = pd.fi.se-1;
if(r < l) continue;
++l, ++r; // do przedzialowca
int sz = 1;
for(int j = i+1; j < n-1; ++j) if(mp[j][pd.fi]) ++sz, mp[j][pd.fi] = 0;
else break;
for(int j = i; j < i+sz; ++j){
//~ printf("%d %d %d: %lld\n", j, l-1, r-1, result);
for(int &x : rem[j-i]) seg.update(x, 0);
rem[j-i].clear();
int endpoint = segm[j-1].query_min(l, r);
if(j < endpoint){
seg.update(j-i+1, 1);
rem[min(sz, endpoint-i)].emplace_back(j-i+1);
}
endpoint = segm[j+1].query_max(l, r);
result += seg.query(max(-1, endpoint-i)+2, j-i+1);
//~ printf("%d %d %d: %d %lld\n", j, l-1, r-1, endpoint, result);
}
for(int &x : rem[sz]) seg.update(x, 0);
rem[sz].clear();
}
}
return result;
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ){
int n, m; scanf("%d%d", &n, &m);
vv<vv<int>> t(n, vv<int>(m, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) scanf("%d", &t[i][j]);
ll result = count_rectangles(t);
printf("%lld\n", result);
}
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
580 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
580 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
3 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1368 KB |
Output is correct |
24 |
Correct |
3 ms |
1572 KB |
Output is correct |
25 |
Correct |
3 ms |
1280 KB |
Output is correct |
26 |
Correct |
5 ms |
1628 KB |
Output is correct |
27 |
Correct |
5 ms |
1628 KB |
Output is correct |
28 |
Correct |
4 ms |
1628 KB |
Output is correct |
29 |
Correct |
2 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
580 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1372 KB |
Output is correct |
18 |
Correct |
3 ms |
1368 KB |
Output is correct |
19 |
Correct |
3 ms |
1572 KB |
Output is correct |
20 |
Correct |
3 ms |
1280 KB |
Output is correct |
21 |
Correct |
5 ms |
1628 KB |
Output is correct |
22 |
Correct |
5 ms |
1628 KB |
Output is correct |
23 |
Correct |
4 ms |
1628 KB |
Output is correct |
24 |
Correct |
2 ms |
860 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
17 ms |
7000 KB |
Output is correct |
31 |
Correct |
17 ms |
7004 KB |
Output is correct |
32 |
Correct |
17 ms |
7004 KB |
Output is correct |
33 |
Correct |
20 ms |
6076 KB |
Output is correct |
34 |
Correct |
29 ms |
8788 KB |
Output is correct |
35 |
Correct |
29 ms |
8784 KB |
Output is correct |
36 |
Correct |
27 ms |
8272 KB |
Output is correct |
37 |
Correct |
27 ms |
8536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
580 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1372 KB |
Output is correct |
18 |
Correct |
3 ms |
1368 KB |
Output is correct |
19 |
Correct |
3 ms |
1572 KB |
Output is correct |
20 |
Correct |
3 ms |
1280 KB |
Output is correct |
21 |
Correct |
5 ms |
1628 KB |
Output is correct |
22 |
Correct |
5 ms |
1628 KB |
Output is correct |
23 |
Correct |
4 ms |
1628 KB |
Output is correct |
24 |
Correct |
2 ms |
860 KB |
Output is correct |
25 |
Correct |
17 ms |
7000 KB |
Output is correct |
26 |
Correct |
17 ms |
7004 KB |
Output is correct |
27 |
Correct |
17 ms |
7004 KB |
Output is correct |
28 |
Correct |
20 ms |
6076 KB |
Output is correct |
29 |
Correct |
29 ms |
8788 KB |
Output is correct |
30 |
Correct |
29 ms |
8784 KB |
Output is correct |
31 |
Correct |
27 ms |
8272 KB |
Output is correct |
32 |
Correct |
27 ms |
8536 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
229 ms |
82488 KB |
Output is correct |
39 |
Correct |
245 ms |
82260 KB |
Output is correct |
40 |
Correct |
222 ms |
82336 KB |
Output is correct |
41 |
Correct |
240 ms |
82544 KB |
Output is correct |
42 |
Correct |
348 ms |
82416 KB |
Output is correct |
43 |
Correct |
332 ms |
82508 KB |
Output is correct |
44 |
Correct |
338 ms |
82772 KB |
Output is correct |
45 |
Correct |
326 ms |
77500 KB |
Output is correct |
46 |
Correct |
186 ms |
65364 KB |
Output is correct |
47 |
Correct |
228 ms |
73044 KB |
Output is correct |
48 |
Correct |
392 ms |
105724 KB |
Output is correct |
49 |
Correct |
411 ms |
107608 KB |
Output is correct |
50 |
Correct |
199 ms |
53736 KB |
Output is correct |
51 |
Correct |
206 ms |
53972 KB |
Output is correct |
52 |
Correct |
375 ms |
97872 KB |
Output is correct |
53 |
Correct |
382 ms |
98644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1628 KB |
Output is correct |
2 |
Correct |
3 ms |
1372 KB |
Output is correct |
3 |
Correct |
2 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
1628 KB |
Output is correct |
6 |
Correct |
4 ms |
1628 KB |
Output is correct |
7 |
Correct |
4 ms |
1624 KB |
Output is correct |
8 |
Correct |
4 ms |
1628 KB |
Output is correct |
9 |
Correct |
4 ms |
1628 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1195 ms |
393108 KB |
Output is correct |
8 |
Correct |
2565 ms |
840132 KB |
Output is correct |
9 |
Correct |
2496 ms |
844144 KB |
Output is correct |
10 |
Correct |
2680 ms |
844132 KB |
Output is correct |
11 |
Correct |
789 ms |
324624 KB |
Output is correct |
12 |
Correct |
1565 ms |
626292 KB |
Output is correct |
13 |
Correct |
1660 ms |
657060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
1 ms |
580 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1372 KB |
Output is correct |
18 |
Correct |
3 ms |
1368 KB |
Output is correct |
19 |
Correct |
3 ms |
1572 KB |
Output is correct |
20 |
Correct |
3 ms |
1280 KB |
Output is correct |
21 |
Correct |
5 ms |
1628 KB |
Output is correct |
22 |
Correct |
5 ms |
1628 KB |
Output is correct |
23 |
Correct |
4 ms |
1628 KB |
Output is correct |
24 |
Correct |
2 ms |
860 KB |
Output is correct |
25 |
Correct |
17 ms |
7000 KB |
Output is correct |
26 |
Correct |
17 ms |
7004 KB |
Output is correct |
27 |
Correct |
17 ms |
7004 KB |
Output is correct |
28 |
Correct |
20 ms |
6076 KB |
Output is correct |
29 |
Correct |
29 ms |
8788 KB |
Output is correct |
30 |
Correct |
29 ms |
8784 KB |
Output is correct |
31 |
Correct |
27 ms |
8272 KB |
Output is correct |
32 |
Correct |
27 ms |
8536 KB |
Output is correct |
33 |
Correct |
229 ms |
82488 KB |
Output is correct |
34 |
Correct |
245 ms |
82260 KB |
Output is correct |
35 |
Correct |
222 ms |
82336 KB |
Output is correct |
36 |
Correct |
240 ms |
82544 KB |
Output is correct |
37 |
Correct |
348 ms |
82416 KB |
Output is correct |
38 |
Correct |
332 ms |
82508 KB |
Output is correct |
39 |
Correct |
338 ms |
82772 KB |
Output is correct |
40 |
Correct |
326 ms |
77500 KB |
Output is correct |
41 |
Correct |
186 ms |
65364 KB |
Output is correct |
42 |
Correct |
228 ms |
73044 KB |
Output is correct |
43 |
Correct |
392 ms |
105724 KB |
Output is correct |
44 |
Correct |
411 ms |
107608 KB |
Output is correct |
45 |
Correct |
199 ms |
53736 KB |
Output is correct |
46 |
Correct |
206 ms |
53972 KB |
Output is correct |
47 |
Correct |
375 ms |
97872 KB |
Output is correct |
48 |
Correct |
382 ms |
98644 KB |
Output is correct |
49 |
Correct |
4 ms |
1628 KB |
Output is correct |
50 |
Correct |
3 ms |
1372 KB |
Output is correct |
51 |
Correct |
2 ms |
1116 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
4 ms |
1628 KB |
Output is correct |
54 |
Correct |
4 ms |
1628 KB |
Output is correct |
55 |
Correct |
4 ms |
1624 KB |
Output is correct |
56 |
Correct |
4 ms |
1628 KB |
Output is correct |
57 |
Correct |
4 ms |
1628 KB |
Output is correct |
58 |
Correct |
1 ms |
724 KB |
Output is correct |
59 |
Correct |
2 ms |
1116 KB |
Output is correct |
60 |
Correct |
1 ms |
348 KB |
Output is correct |
61 |
Correct |
1195 ms |
393108 KB |
Output is correct |
62 |
Correct |
2565 ms |
840132 KB |
Output is correct |
63 |
Correct |
2496 ms |
844144 KB |
Output is correct |
64 |
Correct |
2680 ms |
844132 KB |
Output is correct |
65 |
Correct |
789 ms |
324624 KB |
Output is correct |
66 |
Correct |
1565 ms |
626292 KB |
Output is correct |
67 |
Correct |
1660 ms |
657060 KB |
Output is correct |
68 |
Correct |
1 ms |
348 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
1 ms |
348 KB |
Output is correct |
71 |
Correct |
0 ms |
348 KB |
Output is correct |
72 |
Correct |
0 ms |
348 KB |
Output is correct |
73 |
Correct |
3151 ms |
1048576 KB |
Output is correct |
74 |
Correct |
3407 ms |
1048576 KB |
Output is correct |
75 |
Correct |
3050 ms |
1048576 KB |
Output is correct |
76 |
Correct |
3328 ms |
1048576 KB |
Output is correct |
77 |
Execution timed out |
5078 ms |
1048576 KB |
Time limit exceeded |
78 |
Halted |
0 ms |
0 KB |
- |