<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:
        n = len(s)
        #c0**2<=c1
        ans = 0
        cnt = [[0] * (n+1) for _ in range(2)]
        
        s1 = [0] * (n)
        s2 = [0] * (n)
        c1 = 0
        for i in range(n):
            cnt[0][i+1] = cnt[0][i] + (s[i]=='0')
            cnt[1][i+1] = cnt[1][i] + (s[i]=='1')
            if s[i] == '1':
                s1[i] = c1 + 1
                c1 += 1
            else:
                if c1 > 0:
                    ans += c1 * (c1 + 1) // 2
                s1[i] = 0
                c1 = 0
        if c1 > 0:
            s1[-1] = c1
            ans += c1 * (c1 + 1) // 2
        c1 = 0
        next0 = [0] * (n)
        nxt = n
        for i in range(n-1, -1, -1):
            if s[i] == '0':
                next0[i] = nxt
                nxt = i
            if s[i] == '1':
                s2[i] = c1 + 1
                c1 += 1
            else:
                s2[i] = 0
                c1 = 0
        if c1 > 0:
            s2[0] = c1
        m = int(sqrt(n))
        # print(next0)
        # print(cnt[1][:])
        # print("s2", s2)
        next01 = [n] * (n+1)
        for i in range(n-1, -1, -1):
            if s[i] == '1':
                next01[i] = i
            else:
                next01[i] = next01[i+1]
        # print(next01)
        # ans=0
        for i in range(n):
            if s[i] == '0':
                j = i
                c0 = 0
                while j < n:
                    c0 += 1
                    x, y = s1[i-1], s2[j]
                    if i == 0 or s[i-1] == '0':
                        x = 0
                    else:
                        x = s1[i-1]
                    if j == n - 1 or s[j+1] == '0':
                        y = 0
                    else:
                        y = s2[j+1]
                    # print(i, j, s[i:j+1], x, y)
                    c1 = cnt[1][j+1] - cnt[1][i]
                    # print("c1", cnt[1][j+1], cnt[1][x])
                    d = c1 - c0**2
                    delta = 0
                    if d >= 0:
                        delta = (x+1)*(y+1)
                    else:
                        # print("YES", d)
                        d = -d
                        if x + y - d >= 0:
                            # d = x + y - d
                            xx = x
                            
                            while xx >= 0:
                                # print(f"d={d},xx={xx},y={y}")
                                delta += max(0,1 + y - max(0, d - xx))
                                xx -= 1
                    ans += delta
                    # print("delta", delta)
                    j = next0[j]
                    if c0 > m:
                        break
        return ans
        
23600