Submission #785569

#	Time	Username	Problem	Language	Result	Execution time	Memory
785569		flappybird	Raspad (COI17_raspad)	C++17	9 / 100	6031 ms	14452 KiB

raspad

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 103030
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N, M;
int mcnt;
int pcnt;
int mp[MAX][60], col[MAX][60];
int p[MAX * 55];
int endtime[2][60];
ll ans;
int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}
int uni(int a, int b, int c, int t) {
	a = find(a);
	b = find(b);
	if (a == b) return 0;
	if (a > b) swap(a, b);
	if (b <= mcnt) endtime[c][b] = t, pcnt++;
	p[b] = a;
	return 1;
}
ll naive(int l, int r) {
	int i, j;
	int cnt = 0;
	int rcnt = 0;
	ll ans = 0;
	for (i = l; i <= r; i++) {
		for (j = 1; j <= M; j++) {
			if (mp[i][j]) {
				cnt++;
				col[i][j] = cnt;
				p[cnt] = cnt;
				if (mp[i - 1][j]) {
					if (i > l && uni(col[i - 1][j], col[i][j], 1, 1)) rcnt++;
				}
				if (mp[i][j - 1]) {
					if (uni(col[i][j - 1], col[i][j], 1, 1)) rcnt++;
				}
			}
		}
	}
	return cnt - rcnt;
}
void solve(int l, int r) {
	if (l > r) return;
	int i, j;
	int m = l + r >> 1;
	int pv = 0;
	int cnt = 0, rcnt = 0;
	for (i = 1; i <= M; i++) {
		if (mp[m][i]) {
			if (!pv) {
				cnt++;
				p[cnt] = cnt;
				col[m][i] = cnt;
				pv = 1;
			}
			else col[m][i] = col[m][i - 1];
		}
		else pv = 0;
	}
	if (l == r) {
		ans += cnt;
		return;
	}
	mcnt = cnt;
	for (i = 1; i <= mcnt; i++) endtime[0][i] = l - 1, endtime[1][i] = r + 1;
	pcnt = 0;
	for (i = m - 1; i >= l; i--) {
		for (j = 1; j <= M; j++) {
			if (mp[i][j]) {
				if (mp[i][j - 1]) col[i][j] = cnt;
				else col[i][j] = ++cnt, p[cnt] = cnt;
				if (mp[i + 1][j]) rcnt += uni(col[i][j], col[i + 1][j], 0, i);
			}
		}
		int rem = cnt - rcnt - mcnt + pcnt;
		ans += 1ll * rem * (r - m + 1);
	}
	cnt = mcnt;
	for (i = 1; i <= mcnt; i++) p[i] = i;
	pcnt = 0;
	rcnt = 0;
	for (i = m + 1; i <= r; i++) {
		for (j = 1; j <= M; j++) {
			if (mp[i][j]) {
				if (mp[i][j - 1]) col[i][j] = cnt;
				else col[i][j] = ++cnt, p[cnt] = cnt;
				if (mp[i - 1][j]) rcnt += uni(col[i][j], col[i - 1][j], 1, i);
			}
		}
		int rem = cnt - rcnt - mcnt + pcnt;
		ans += 1ll * rem * (m - l + 1);
	}
	for (i = 1; i <= mcnt; i++) ans += 1ll * (m - endtime[0][i]) * (endtime[1][i] - m);
	solve(l, m - 1);
	solve(m + 1, r);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i, j;
	string s;
	for (i = 1; i <= N; i++) {
		cin >> s;
		for (j = 1; j <= M; j++) mp[i][j] = s[j - 1] == '1';
	}
	//solve(1, N);
	ll ans = 0;
	for (i = 1; i <= N; i++) for (j = i; j <= N; j++) ans += naive(i, j);
	cout << ans << ln;
}

Compilation message (stderr)

raspad.cpp: In function 'll naive(int, int)':
raspad.cpp:40:5: warning: unused variable 'ans' [-Wunused-variable]
   40 |  ll ans = 0;
      |     ^~~
raspad.cpp: In function 'void solve(int, int)':
raspad.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39