#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
ll count_rectangles(vector<vi> a){
int n = siz(a), m = siz(a[0]); ll ans = 0;
auto precalc = [&](vector<vi> b){
int N = siz(b), M = siz(b[0]);
auto go = [&](vi v){
stack<pii> s;
vi res(M);
F0R(i, M){
while(siz(s)&&s.top().f<v[i]){
s.pop();
}
if(!siz(s)) res[i]=-1;
else res[i]=s.top().s;
s.push({v[i], i});
}
return res;
};
vector<vector<vpii>> res(N, vector<vpii>(M));
F0R(i, N){
vi l = go(b[i]);
reverse(all(b[i]));
vi r = go(b[i]);
reverse(all(b[i]));
reverse(all(r));
F0R(j, M){
if(r[j]!=-1) r[j]=M-1-r[j];
}
F0R(j, M){
if(l[j]!=-1&&l[j]!=j-1){
res[i][j-1].pb({l[j]+1, 1});
}
}
F0R(j, M){
if(r[j]!=-1&&r[j]!=j+1){
res[i][r[j]-1].pb({j+1, 1});
}
}
F0R(j, M){
sort(all(res[i][j]));
res[i][j].resize(unique(all(res[i][j]))-res[i][j].begin());
}
}
F0R(i, N-1){
F0R(j, M){
trav(x, res[i][j]){
trav(y, res[i+1][j]){
if(x.f==y.f){
y.s = x.s+1;
}
}
}
}
}
return res;
};
vector<vector<vpii>> x = precalc(a);
vector<vi> c(m, vi(n));
F0R(i, n)
F0R(j, m)
c[j][i]=a[i][j];
vector<vector<vpii>> y2 = precalc(c);
vector<vector<vpii>> y(n, vector<vpii>(m));
F0R(i, n)
F0R(j, m)
y[i][j]=y2[j][i];
F0R(i, n){
F0R(j, m){
trav(v, x[i][j]){
trav(v2, y[i][j]){
if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
ans++;
}
}
}
}
}
return ans;
}
//int32_t main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// int N, M; cin >> N >> M;
// vector<vi> inp(N, vi(M));
// F0R(i, N){
// F0R(j, M){
// cin >> inp[i][j];
// }
// }
// cout << count_rectangles(inp) << nl;
// return 0;
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
10 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
10 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
9 ms |
1132 KB |
Output is correct |
23 |
Correct |
10 ms |
1152 KB |
Output is correct |
24 |
Correct |
9 ms |
1132 KB |
Output is correct |
25 |
Correct |
4 ms |
1132 KB |
Output is correct |
26 |
Correct |
5 ms |
1408 KB |
Output is correct |
27 |
Correct |
5 ms |
1260 KB |
Output is correct |
28 |
Correct |
5 ms |
1132 KB |
Output is correct |
29 |
Correct |
3 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
10 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
9 ms |
1132 KB |
Output is correct |
18 |
Correct |
10 ms |
1152 KB |
Output is correct |
19 |
Correct |
9 ms |
1132 KB |
Output is correct |
20 |
Correct |
4 ms |
1132 KB |
Output is correct |
21 |
Correct |
5 ms |
1408 KB |
Output is correct |
22 |
Correct |
5 ms |
1260 KB |
Output is correct |
23 |
Correct |
5 ms |
1132 KB |
Output is correct |
24 |
Correct |
3 ms |
748 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
512 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
128 ms |
5100 KB |
Output is correct |
31 |
Correct |
125 ms |
4972 KB |
Output is correct |
32 |
Correct |
117 ms |
5100 KB |
Output is correct |
33 |
Correct |
21 ms |
5100 KB |
Output is correct |
34 |
Correct |
28 ms |
6016 KB |
Output is correct |
35 |
Correct |
32 ms |
6124 KB |
Output is correct |
36 |
Correct |
28 ms |
5868 KB |
Output is correct |
37 |
Correct |
28 ms |
6016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
10 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
9 ms |
1132 KB |
Output is correct |
18 |
Correct |
10 ms |
1152 KB |
Output is correct |
19 |
Correct |
9 ms |
1132 KB |
Output is correct |
20 |
Correct |
4 ms |
1132 KB |
Output is correct |
21 |
Correct |
5 ms |
1408 KB |
Output is correct |
22 |
Correct |
5 ms |
1260 KB |
Output is correct |
23 |
Correct |
5 ms |
1132 KB |
Output is correct |
24 |
Correct |
3 ms |
748 KB |
Output is correct |
25 |
Correct |
128 ms |
5100 KB |
Output is correct |
26 |
Correct |
125 ms |
4972 KB |
Output is correct |
27 |
Correct |
117 ms |
5100 KB |
Output is correct |
28 |
Correct |
21 ms |
5100 KB |
Output is correct |
29 |
Correct |
28 ms |
6016 KB |
Output is correct |
30 |
Correct |
32 ms |
6124 KB |
Output is correct |
31 |
Correct |
28 ms |
5868 KB |
Output is correct |
32 |
Correct |
28 ms |
6016 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
512 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
285 ms |
50028 KB |
Output is correct |
39 |
Correct |
195 ms |
54892 KB |
Output is correct |
40 |
Correct |
220 ms |
60708 KB |
Output is correct |
41 |
Correct |
281 ms |
65388 KB |
Output is correct |
42 |
Correct |
4261 ms |
57452 KB |
Output is correct |
43 |
Correct |
4287 ms |
57452 KB |
Output is correct |
44 |
Correct |
4233 ms |
57436 KB |
Output is correct |
45 |
Correct |
3899 ms |
54260 KB |
Output is correct |
46 |
Correct |
231 ms |
53228 KB |
Output is correct |
47 |
Correct |
283 ms |
57836 KB |
Output is correct |
48 |
Correct |
391 ms |
68716 KB |
Output is correct |
49 |
Correct |
393 ms |
68716 KB |
Output is correct |
50 |
Correct |
180 ms |
35308 KB |
Output is correct |
51 |
Correct |
190 ms |
35264 KB |
Output is correct |
52 |
Correct |
378 ms |
66540 KB |
Output is correct |
53 |
Correct |
390 ms |
66796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
1516 KB |
Output is correct |
2 |
Correct |
58 ms |
1260 KB |
Output is correct |
3 |
Correct |
4 ms |
1260 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
6 ms |
1388 KB |
Output is correct |
6 |
Correct |
6 ms |
1388 KB |
Output is correct |
7 |
Correct |
6 ms |
1388 KB |
Output is correct |
8 |
Correct |
6 ms |
1388 KB |
Output is correct |
9 |
Correct |
5 ms |
1536 KB |
Output is correct |
10 |
Correct |
4 ms |
876 KB |
Output is correct |
11 |
Correct |
6 ms |
1132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1419 ms |
304864 KB |
Output is correct |
8 |
Correct |
3050 ms |
658368 KB |
Output is correct |
9 |
Correct |
2979 ms |
662532 KB |
Output is correct |
10 |
Correct |
3110 ms |
662672 KB |
Output is correct |
11 |
Correct |
951 ms |
255852 KB |
Output is correct |
12 |
Correct |
1847 ms |
484460 KB |
Output is correct |
13 |
Correct |
1910 ms |
516272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
10 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
9 ms |
1132 KB |
Output is correct |
18 |
Correct |
10 ms |
1152 KB |
Output is correct |
19 |
Correct |
9 ms |
1132 KB |
Output is correct |
20 |
Correct |
4 ms |
1132 KB |
Output is correct |
21 |
Correct |
5 ms |
1408 KB |
Output is correct |
22 |
Correct |
5 ms |
1260 KB |
Output is correct |
23 |
Correct |
5 ms |
1132 KB |
Output is correct |
24 |
Correct |
3 ms |
748 KB |
Output is correct |
25 |
Correct |
128 ms |
5100 KB |
Output is correct |
26 |
Correct |
125 ms |
4972 KB |
Output is correct |
27 |
Correct |
117 ms |
5100 KB |
Output is correct |
28 |
Correct |
21 ms |
5100 KB |
Output is correct |
29 |
Correct |
28 ms |
6016 KB |
Output is correct |
30 |
Correct |
32 ms |
6124 KB |
Output is correct |
31 |
Correct |
28 ms |
5868 KB |
Output is correct |
32 |
Correct |
28 ms |
6016 KB |
Output is correct |
33 |
Correct |
285 ms |
50028 KB |
Output is correct |
34 |
Correct |
195 ms |
54892 KB |
Output is correct |
35 |
Correct |
220 ms |
60708 KB |
Output is correct |
36 |
Correct |
281 ms |
65388 KB |
Output is correct |
37 |
Correct |
4261 ms |
57452 KB |
Output is correct |
38 |
Correct |
4287 ms |
57452 KB |
Output is correct |
39 |
Correct |
4233 ms |
57436 KB |
Output is correct |
40 |
Correct |
3899 ms |
54260 KB |
Output is correct |
41 |
Correct |
231 ms |
53228 KB |
Output is correct |
42 |
Correct |
283 ms |
57836 KB |
Output is correct |
43 |
Correct |
391 ms |
68716 KB |
Output is correct |
44 |
Correct |
393 ms |
68716 KB |
Output is correct |
45 |
Correct |
180 ms |
35308 KB |
Output is correct |
46 |
Correct |
190 ms |
35264 KB |
Output is correct |
47 |
Correct |
378 ms |
66540 KB |
Output is correct |
48 |
Correct |
390 ms |
66796 KB |
Output is correct |
49 |
Correct |
104 ms |
1516 KB |
Output is correct |
50 |
Correct |
58 ms |
1260 KB |
Output is correct |
51 |
Correct |
4 ms |
1260 KB |
Output is correct |
52 |
Correct |
1 ms |
364 KB |
Output is correct |
53 |
Correct |
6 ms |
1388 KB |
Output is correct |
54 |
Correct |
6 ms |
1388 KB |
Output is correct |
55 |
Correct |
6 ms |
1388 KB |
Output is correct |
56 |
Correct |
6 ms |
1388 KB |
Output is correct |
57 |
Correct |
5 ms |
1536 KB |
Output is correct |
58 |
Correct |
4 ms |
876 KB |
Output is correct |
59 |
Correct |
6 ms |
1132 KB |
Output is correct |
60 |
Correct |
1 ms |
364 KB |
Output is correct |
61 |
Correct |
1419 ms |
304864 KB |
Output is correct |
62 |
Correct |
3050 ms |
658368 KB |
Output is correct |
63 |
Correct |
2979 ms |
662532 KB |
Output is correct |
64 |
Correct |
3110 ms |
662672 KB |
Output is correct |
65 |
Correct |
951 ms |
255852 KB |
Output is correct |
66 |
Correct |
1847 ms |
484460 KB |
Output is correct |
67 |
Correct |
1910 ms |
516272 KB |
Output is correct |
68 |
Correct |
1 ms |
364 KB |
Output is correct |
69 |
Correct |
1 ms |
364 KB |
Output is correct |
70 |
Correct |
1 ms |
364 KB |
Output is correct |
71 |
Correct |
1 ms |
512 KB |
Output is correct |
72 |
Correct |
1 ms |
364 KB |
Output is correct |
73 |
Execution timed out |
5132 ms |
600636 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |