import java.util.*;

public class SubMatrixSum{

	private int[][] arr;
	private int[][] compress;

	public SubMatrixSum(int[][] _arr){
		arr = _arr;
		getCompress();
	}

	private void getCompress(){
		int N=arr.length;
		int M = arr[0].length;
		compress = new int[N][M];

		for (int i=0; i<M; i++) {
			compress[0][i] = arr[0][i];
		}

		for (int i=1; i<N; i++) {
			//System.out.println();
			for (int j=0; j<M;j++ ) {
				compress[i][j] = (arr[i][j] == 0 ? 0: compress[i-1][j] + 1);
				//System.out.print(compress[i][j]+",");
			}
		}
	}

	public int getSubResult(int[] temp){

		int[][] result=getArray(temp);
		int sum = 0;

		// for (int i=0; i<result.length;i++ ) {
		// 	for (int j=0; j<result[i].length; j++) {
		// 		System.out.print(result[i][j]+",");
		// 	}
		// 	System.out.println();
		// }

		for (int i=0; i<result.length;i++ ) {
			if(result[i][1]==result[i][0]&&result[i][0]==0) continue;
			int size = (result[i][1]==-1 ? temp.length : result[i][1]) - result[i][0];
			int low = Math.max(result[i][0]==-1?0:temp[result[i][0]],result[i][1]==-1?0:temp[result[i][1]]);
			int high = temp[i];

			sum+=getNum(low,high,size-1);

		}
		return sum;
	}


	public int getResult(){
		int sum = 0;

		for (int i=0; i<compress.length;i++ ) {
			sum+= getSubResult(compress[i]);
		}
		return sum;
	}



	private int[][] getArray(int[] temp){
		Stack<Integer> stack = new Stack<Integer> ();
		int[][] result = new int[temp.length][2];
		for (int i=0; i<temp.length; i++) {
			if(stack.isEmpty()){
				stack.push(i);
			}else{
				while(!stack.isEmpty()){
					if(temp[stack.peek()] < temp[i]){
						break;
					}
					int cur = stack.pop();
					if(temp[cur] != temp[i]){
						result[cur][0]= stack.isEmpty()?-1:stack.peek();
						result[cur][1]= i;
					}
				}
				stack.push(i);
			}
		}
		while(!stack.isEmpty()){
			int cur = stack.pop();
			result[cur][0]= stack.isEmpty()?-1:stack.peek();
			result[cur][1]= -1;
		}

		return result;
	}

	private int getNum(int start,int end,int length){
		//System.out.println("start="+start+",end="+end+",length="+length);
		return (length*(length+1)/2) * (end-start);
	}

	public static void main(String[] args){
		int[][] arr = new int[][]{
			{1,1,0,1,1,0,1,1,0,1,1},
			{1,1,0,1,1,1,1,1,0,1,1},
			{0,1,1,1,1,1,1,1,1,1,0},
			{1,1,0,1,1,1,1,1,1,1,1},
			{1,1,0,1,1,0,1,1,1,0,1},
		};
		SubMatrixSum ss = new SubMatrixSum(arr);
		System.out.println("Sum = "+ss.getResult());
		System.out.println("Sum = "+numSubmat(arr));
	}






































	public static int numSubmat(int[][] mat) {
		if (mat == null || mat.length == 0 || mat[0].length == 0) {
			return 0;
		}
		int nums = 0;
		int[] height = new int[mat[0].length];
		for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat[0].length; j++) {
				height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
			}
			nums += countFromBottom(height);
		}
		return nums;

	}

	public static int countFromBottom(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}
		int nums = 0;
		int[] stack = new int[height.length];
		int si = -1;
		for (int i = 0; i < height.length; i++) {
			while (si != -1 && height[stack[si]] >= height[i]) {
				int cur = stack[si--];
				if (height[cur] > height[i]) {
					int left = si == -1 ? -1 : stack[si];
					int n = i - left - 1;
					int down = Math.max(left == -1 ? 0 : height[left], height[i]);
					nums += (height[cur] - down) * num(n);
				}

			}
			stack[++si] = i;
		}
		while (si != -1) {
			int cur = stack[si--];
			int left = si == -1  ? -1 : stack[si];
			int n = height.length - left - 1;
			int down = left == -1 ? 0 : height[left];
			nums += (height[cur] - down) * num(n);
		}
		return nums;
	}

	public static int num(int n) {
		return ((n * (1 + n)) >> 1);
	}

}