#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
const int N = 1e5 + 5, M = 50 + 2;
struct disjoint_set_union{
int par[2 * M], val[2 * M];
void reset(int len){
fill(par + 1, par + len + 1, -1);
fill(val + 1, val + len + 1, 0);
}
int root(int x){
return par[x] < 0 ? x : (par[x] = root(par[x]));
}
pii ansmerge;
bool merge(int x, int y){
if ((x = root(x)) == (y = root(y))){
return 0;
}
if (par[x] > par[y]){
swap(x, y);
}
par[x] += par[y];
par[y] = x;
if (val[x] == val[y]){
return 0;
}
ansmerge = make_pair(val[x], val[y]);
if (val[x] == 0){
val[x] = val[y];
}
else if (val[y] == 0){
}
else{
val[x] = min(val[x], val[y]);
}
val[y] = val[x];
return 1;
}
} dsu[3];
int n, m;
char a[N][M];
ll ans;
int pos[2 * M];
void find_interval(const vector <pair <int, pii>> &a, vector <pair <int, pii>> &b){
b.clear();
int l = 0;
ForE(r, 1, isz(a)){
if (r == isz(a) or a[r].fi != a[r - 1].fi){
b.emplace_back(a[l].fi, make_pair(l, r - 1));
l = r;
}
}
}
void divide_and_conquer(int l, int r){
if (l == r){
ForE(j, 1, m){
if (a[l][j - 1] == '0' and a[l][j] == '1'){
ans++;
}
}
return;
}
int mid = (l + r) >> 1;
divide_and_conquer(l, mid);
divide_and_conquer(mid + 1, r);
vector <pair <int, pii>> mergel = {{mid, {0, 0}}}, merger = {{mid + 1, {0, 0}}};
{
int ctridx = 0;
dsu[mid & 1].reset(m);
ForE(j, 1, m){
if (a[mid][j] != '1'){
continue;
}
dsu[mid & 1].val[j] = ++ctridx;
if (a[mid][j - 1] == '1'){
dsu[mid & 1].merge(j - 1, j);
}
}
int idx_colmid = ctridx;
int cnt = 0;
FordE(i, mid - 1, l){
int ii = i & 1;
dsu[ii].reset(m);
ForE(j, 1, m){
if (a[i][j] != '1'){
continue;
}
if (a[i + 1][j] == '1'){
dsu[ii].val[j] = dsu[ii ^ 1].val[j];
}
else{
dsu[ii].val[j] = ++ctridx;
cnt++;
}
if (a[i][j - 1] == '1'){
if (dsu[ii].merge(j - 1, j)){
if (dsu[ii].ansmerge.fi > idx_colmid or dsu[ii].ansmerge.se > idx_colmid){
cnt--;
}
else{
mergel.emplace_back(i, dsu[ii].ansmerge);
}
}
}
}
ans += (ll)cnt * (r - mid);
}
}
// cout << "STEP 1 " << l << ' ' << r << ' ' << ans << endl;
{
int ctridx = 0;
dsu[(mid + 1) & 1].reset(m);
ForE(j, 1, m){
if (a[mid + 1][j] != '1'){
continue;
}
dsu[(mid + 1) & 1].val[j] = ++ctridx;
if (a[mid + 1][j - 1] == '1'){
dsu[(mid + 1) & 1].merge(j - 1, j);
}
}
int idx_colmid = ctridx;
int cnt = 0;
ForE(i, mid + 2, r){
int ii = i & 1;
dsu[ii].reset(m);
ForE(j, 1, m){
if (a[i][j] != '1'){
continue;
}
if (a[i - 1][j] == '1'){
dsu[ii].val[j] = dsu[ii ^ 1].val[j];
}
else{
dsu[ii].val[j] = ++ctridx;
cnt++;
}
if (a[i][j - 1] == '1'){
if (dsu[ii].merge(j - 1, j)){
if (dsu[ii].ansmerge.fi > idx_colmid or dsu[ii].ansmerge.se > idx_colmid){
cnt--;
}
else{
merger.emplace_back(i, dsu[ii].ansmerge);
}
}
}
}
ans += (ll)cnt * (mid - l + 1);
}
}
// cout << "STEP 2 " << l << ' ' << r << ' ' << ans << endl;
// cout << "MERGEL" << endl;
// Fora(elem, mergel){
// cout << elem.fi << ' ' << elem.se.fi << ' ' << elem.se.se << endl;
// }
// cout << "MERGER" << endl;
// Fora(elem, merger){
// cout << elem.fi << ' ' << elem.se.fi << ' ' << elem.se.se << endl;
// }
vector <pair <int, pii>> itvmergel, itvmerger;
find_interval(mergel, itvmergel);
find_interval(merger, itvmerger);
For(il, 0, isz(itvmergel)){
int lenl = itvmergel[il].fi - (il == isz(itvmergel) - 1 ? l - 1 : itvmergel[il + 1].fi);
dsu[2].reset(2 * m);
int cnt = 0, itr = 0;
ForE(j, 1, m){
if (a[mid][j - 1] == '0' and a[mid][j] == '1'){
itr++;
cnt++;
pos[j] = itr;
dsu[2].val[itr] = itr;
}
else if (a[mid][j] == '1'){
itr++;
pos[j] = pos[j - 1];
}
}
if (il != 0){
ForE(til, 1, itvmergel[il].se.se){
if (dsu[2].merge(mergel[til].se.fi, mergel[til].se.se)){
cnt--;
}
}
}
itr = m;
ForE(j, 1, m){
if (a[mid + 1][j - 1] == '0' and a[mid + 1][j] == '1'){
itr++;
cnt++;
pos[j + m] = itr;
dsu[2].val[itr] = itr;
}
else if (a[mid + 1][j] == '1'){
itr++;
pos[j + m] = pos[j + m - 1];
}
if (a[mid][j] == '1' and a[mid + 1][j] == '1'){
if (dsu[2].merge(pos[j], pos[j + m])){
cnt--;
}
}
}
For(ir, 0, isz(itvmerger)){
int lenr = (ir == isz(itvmerger) - 1 ? r + 1 : itvmerger[ir + 1].fi) - itvmerger[ir].fi;
if (ir != 0){
ForE(tir, itvmerger[ir].se.fi, itvmerger[ir].se.se){
if (dsu[2].merge(merger[tir].se.fi + m, merger[tir].se.se + m)){
cnt--;
}
}
}
// cout << "ADD ANS " << il << ' ' << ir << ' ' << lenl << ' ' << lenr << ' ' << cnt << endl;
ans += (ll)lenl * lenr * cnt;
}
}
// cout << "STEP 3 " << l << ' ' << r << ' ' << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n >> m;
ForE(i, 1, n){
ForE(j, 1, m){
cin >> a[i][j];
}
}
ForE(i, 1, n){
a[i][0] = a[i][m + 1] = '0';
}
divide_and_conquer(1, n);
cout << ans << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
2860 KB |
Output is correct |
| 2 |
Incorrect |
307 ms |
5400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
