O(n) solution using pre-computation


#1
int Solution::solve(vector &A, int B) {
    int n = (int)A.size();
    vector<int> odd;
    odd.push_back(-1);
    for(int i=0;i<n;i++)
        if(A[i]%2)
            odd.push_back(i);
    odd.push_back(n);
    int ans = 0;
    if(!B)
    {
        for(int i=1;i<(int)odd.size();i++)
           ans += ((odd[i]-odd[i-1]-1)*(odd[i]-odd[i-1]))/2;
    }
    else
    {
        for(int i=1;i+B<(int)odd.size();i++)
            ans += ((odd[i]-odd[i-1]) * (odd[i+B]-odd[i+B-1]));
    }
    return ans;
}