Submission #1321036

#TimeUsernameProblemLanguageResultExecution timeMemory
1321036NikoBaoticRaspad (COI17_raspad)C++20
100 / 100
1674 ms26744 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 1e5 + 10;
const int M = 53;

int n, m;
char a[N][M];
int b[N][M];
int del[N];
bool rem[M];
ll cur;

int par[M * 2];
int sz[M * 2];
int mi[M * 2];
int ma[M * 2];
int f[M * 2];

int find(int x) {
	if (x == par[x]) return x;
	return par[x] = find(par[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y) return;

	if (sz[x] < sz[y]) swap(x, y);

	sz[x] += sz[y];
	par[y] = x;

	mi[x] = min(mi[x], mi[y]);
	ma[x] = max(ma[x], ma[y]);

	if (min(f[x], f[y]) >= M) {
		f[x] = min(f[x], f[y]);
	} else {
		f[x] = max(f[x], f[y]);
	}
}

void update(int ind) {
	if (ind == n) return;

	for (int i = 0; i < M * 2; i++) {
		par[i] = i;
		mi[i] = i;
		ma[i] = i;
		f[i] = i;
		sz[i] = 1;
	}

	for (int i = 0; i < m; i++) {
		if (b[ind - 1][i] != INT_MAX) merge(b[ind - 1][i], i);	
		if (b[ind][i] != INT_MAX) merge(b[ind][i] + M, i + M);
	}

	int d = 0;

	for (int i = 0; i < m; i++) {
		if (find(i) == i and a[ind - 1][i] == '1') {
			d--;
		}
	}

	for (int i = 0; i < m; i++) {
		if (b[ind - 1][i] != INT_MAX and b[ind][i] != INT_MAX) {
			merge(i, i + M);
		}
	}

	bool ch = 0;

	for (int i = 0; i < m; i++) {
		if (b[ind][i] != INT_MAX and b[ind][i] != f[find(i + M)] - M) {
			ch = 1;
			b[ind][i] = f[find(i + M)] - M;	
		}
	}

	for (int i = 0; i < m; i++) {
		if (ma[find(i + M)] == i + M and a[ind][i] == '1') {
			if (mi[find(i + M)] >= M) {
				d++;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		if (mi[find(i)] == i and a[ind - 1][i] == '1') {
			d++;
		}
	}

	if (d != del[ind]) {
		cur += -del[ind] * (n - ind) + d * (n - ind);
		del[ind] = d;

	}

	if (ch) update(ind + 1);
}

int main() {
	FIO;
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}

	ll ans = 0;

	for (int i = n - 1; i >= 0; i--) {
		char last = '0';
		int cnt = 0;
	
		for (int j = 0; j < m; j++) {
			if (a[i][j] == '1') {
				if (last == '1') {
					b[i][j] = b[i][j - 1];
				} else {
					b[i][j] = j;
					cnt++;
				}
			} else {
				b[i][j] = INT_MAX;
			}

			last = a[i][j];
		}

		cur += cnt * (n - i);

		del[i] = cnt;

		update(i + 1);

		ans += cur;
	}

	cout << ans << endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...