Number of submatrices with OR value 1 | C ++ program to count number of submatrices with OR value 1 ; Function to find required prefix - count for each row from right to left ; Function to find the count of submatrices with OR value 1 ; Array to store prefix count of zeros from right to left for boolean array ; Variable to store the count of submatrices with OR value 0 ; Loop to evaluate each column of the prefix matrix uniquely . For each index of a column we will try to determine the number of sub - matrices starting from that index and has all 1 s ; First part of pair will be the value of inserted element . Second part will be the count of the number of elements pushed before with a greater value ; Variable to store the number of submatrices with all 0 s ; Return the final answer ; Driver Code
#include <iostream> NEW_LINE #include <stack> NEW_LINE #define n  3 NEW_LINE using namespace std ; void findPrefixCount ( int p_arr [ ] [ n ] , bool arr [ ] [ n ] ) { for ( int i = 0 ; i < n ; i ++ ) for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( arr [ i ] [ j ] ) continue ; if ( j != n - 1 ) p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] ; p_arr [ i ] [ j ] += ( int ) ( ! arr [ i ] [ j ] ) ; } } int matrixOrValueOne ( bool arr [ ] [ n ] ) { int p_arr [ n ] [ n ] = { 0 } ; findPrefixCount ( p_arr , arr ) ; int count_zero_submatrices = 0 ; for ( int j = 0 ; j < n ; j ++ ) { int i = n - 1 ; stack < pair < int , int > > q ; int to_sum = 0 ; while ( i >= 0 ) { int c = 0 ; while ( q . size ( ) != 0 and q . top ( ) . first > p_arr [ i ] [ j ] ) { to_sum -= ( q . top ( ) . second + 1 ) * ( q . top ( ) . first - p_arr [ i ] [ j ] ) ; c += q . top ( ) . second + 1 ; q . pop ( ) ; } to_sum += p_arr [ i ] [ j ] ; count_zero_submatrices += to_sum ; q . push ( { p_arr [ i ] [ j ] , c } ) ; i -- ; } } return ( n * ( n + 1 ) * n * ( n + 1 ) ) / 4 - count_zero_submatrices ; } int main ( ) { bool arr [ ] [ n ] = { { 0 , 0 , 0 } , { 0 , 1 , 0 } , { 0 , 0 , 0 } } ; cout << matrixOrValueOne ( arr ) ; return 0 ; }