<p>You are given a binary string <code>s</code>.</p>

<p>Return the number of <span data-keyword="substring-nonempty">substrings</span> with <strong>dominant</strong> ones.</p>

<p>A string has <strong>dominant</strong> ones if the number of ones in the string is <strong>greater than or equal to</strong> the <strong>square</strong> of the number of zeros in the string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;00011&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with dominant ones are shown in the table below.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>3</td>
			<td>3</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>2</td>
			<td>3</td>
			<td>01</td>
			<td>1</td>
			<td>1</td>
		</tr>
		<tr>
			<td>3</td>
			<td>4</td>
			<td>11</td>
			<td>0</td>
			<td>2</td>
		</tr>
		<tr>
			<td>2</td>
			<td>4</td>
			<td>011</td>
			<td>1</td>
			<td>2</td>
		</tr>
	</tbody>
</table>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;101101&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">16</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with <strong>non-dominant</strong> ones are shown in the table below.</p>

<p>Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>1</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>1</td>
			<td>4</td>
			<td>0110</td>
			<td>2</td>
			<td>2</td>
		</tr>
		<tr>
			<td>0</td>
			<td>4</td>
			<td>10110</td>
			<td>2</td>
			<td>3</td>
		</tr>
		<tr>
			<td>1</td>
			<td>5</td>
			<td>01101</td>
			<td>2</td>
			<td>3</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists only of characters <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        prefix_1 = [0]
        for ch in s:
            prefix_1.append(prefix_1[-1] + int(ch == '1'))

        zeroes = []
        ones = []
        res = 0
        for i, ch in enumerate(s):
            prev_index = i + 1
            curr_i = i
            prev_tmp = False

            while True:
                num1 = prefix_1[i + 1] - prefix_1[curr_i]
                num0 = (i - curr_i + 1) - num1
                #print(i, num0, num1)
                tmp = num1 >= num0 ** 2

                if tmp:
                    nval = prev_index - curr_i if prev_tmp else 1
                    res += prev_index - curr_i if prev_tmp else 1
                    #print("found: ", prev_index - curr_i + 1)
                    diff = max(1, int((num1 ** 0.5) - num0))
                    zi = len(zeroes) - diff - num0 + int(ch == '0')
                    next_index = zeroes[zi] if 0 <= zi < len(zeroes) else 0
                    #print(f"i {i}; num0 {num0}; num1 {num1}; zi {zi}; next_index {next_index}; zeroes {zeroes}")
                    #print(f"i {i}; num0 {num0}; num1 {num1}; diff {diff}; nval {nval}; curr_i {curr_i}; prev_index {prev_index}")
                else:
                    res += prev_index - curr_i - 1 if prev_tmp else 0
                    diff = max(1, num0 ** 2 - num1)
                    zi = len(ones) - diff - num1 + int(ch == '1')
                    next_index = ones[zi] if 0 <= zi < len(ones) else 0
                    #print(f"i {i}; num0 {num0}; num1 {num1}; not nval; next_index {next_index}")
                #print(f"new diff: {diff}")
                if not curr_i:
                    break

                prev_tmp = tmp
                prev_index = curr_i
                curr_i = next_index
            
            if ch == '0':
                zeroes.append(i)
            else:
                ones.append(i)

        return res
20100