1398F - Controversial Rounds - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2000005;

int read()
{
	int f = 1, k = 0;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
		{
			f = -1;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		k = k * 10 + c - '0';
		c = getchar();
	}
	return f * k;
}

int n, m, k, tt, cnt, ans, pre[N][2];

string s;

signed main()
{
	scanf("%d", &n);
	cin >> s;
	for (int i = 0; i < n; i++)
	{
		pre[i + 1][0] = pre[i][0];
		pre[i + 1][1] = pre[i][1];
		if (s[i] == '?')
		{
			continue;
		}
		pre[i + 1][s[i] & 1 ^ 1] = i + 1;
	}
	for (int len = 1; len <= n; len++)
	{
		int p = 0, ans = 0;
		while (p + len <= n)
		{
			if (pre[p + len][0] == pre[p][0] || pre[p + len][1] == pre[p][1])
			{
				p += len;
				ans++;
			}
			else
			{
				p = pre[p + len][pre[p + len][1] < pre[p + len][0]];
			}
		}
		cout << ans << " ";
	}
	return 0;
}